On the Necessity of Collaboration for Online Model Selection with Decentralized Data
Authors: Junfan Li
Zheshun Wu
Zenglin Xu
Irwin King
Venue: NeurIPS 2024 poster (2024)
Keywords: online learning
model selection
federated learning
kernel methods
Primary area: online_learning
TL;DR: We clarify the unnecessary nature of collaboration in previous federated online model selection algorithms,  and give conditions under which collaboration is necessary.

Abstract: We consider online model selection with decentralized data over $M$ clients, and study the necessity of collaboration among clients. Previous work proposed various federated algorithms without demonstrating their necessity, while we answer the question from a novel perspective of computational constraints. We prove lower bounds on the regret, and propose a federated algorithm and analyze the upper bound. Our results show (i) collaboration is unnecessary in the absence of computational constraints on clients; (ii) collaboration is necessary if the computational cost on each client is limited to $o(K)$, where $K$ is the number of candidate hypothesis spaces. We clarify the unnecessary nature of collaboration in previous federated algorithms for distributed online multi-kernel learning, and improve the regret bounds at a smaller computational and communication cost. Our algorithm relies on three new techniques including an improved Bernstein's inequality for martingale, a federated online mirror descent framework, and decoupling model selection and prediction, which might be of independent interest.

On the Necessity of Collaboration for Online Model Selection with Decentralized Data
Junfan Li
Zheshun Wu Zenglin 232.3,4 Irwin King"
School of Computer Science and Technology, Harbin Institute of Technology, Shenzhen
Pengcheng Lab
3 Artificial Intelligence Innovation and Incubation (AI") Institute, Fudan University
'Shanghai Academy of AI for Science
DDepartment of Computer Science and Engineering. The Chinese University of Hong Kong
lijunfan@hit. edu.cc wuzhsh23dgmail. com zenglin@gmail com kingScse. cuhk. edu. hk
Abstract
We consider online model selection with decentralized data over M clients, and study the necessity of collaboration among clients. Previous work proposed various federated algorithms without demonstrating their necessity, while we answer the question from a novel perspective computational constraints. We prove lower bounds on the regret, and propose a federated algorithm and analyze the upper bound. Our results show (i) collaboration is unnecessary in the absence compu- tational constraints on clients; (ii) collaboration is necessary if the computational cost on each client is limited
((),, where K is the number of candidate hy- pothesis spaces. We clarify the unnecessary nature of collaboration in previous federated algorithms for distributed online multi-kernel learning, and improve the regret bounds smaller computational and communication cost. Our algorithm relies on three new techniques including an improved Bernstein's 's inequality for martingale, federated online mirror descent framework, and decoupling model selection and prediction, which might be independent interest.
1 Introduction
Model selection which a fundamental problem for offline machine learning focuses on how to select
suitable hypothesis space for a machine learning algorithm [itchell| 1997 Bartlett et al. 2002
Mohri et al. (2018). Model selection for online machine learning is called online model selection
(OMS), such as model selection for online supervised learning [Foster et al. 2017 Zhang and Liao
2018 Zhang et al. 2021 Li and Liao| 2022], model selection for online active learning [Krimi al. 2021]. J. and model selection for contextual bandits [Foster al. 2019 Pacchiano et al. 2020
Ghosh and Chowdhury 2022). We consider model selection for online supervised learning. Let
F [Fi...., ......FK) contain K hypothesis spaces and E(...) be loss function. For sequence of examples [(x,, b=),.= we aim to adapt to the case that the optimal hypothesis space Fi. E F given by an oracle and minimizing the regret, i.e.
online learning algorithm in Fr.. OMS can be defined by
Σ ((f(x)))))) min fEF
Ee(((x))v)))
min Secorf Fr
"Corresponding author.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

F; is the hypothesis used by an OMS algorithm at the t-th round. The optimal value where fi I of the regret depends on the complexity of F₁, Fooster al. 2017 2019].
In this work, we consider online model selection with decentralized data (OMS-DecD) over M clients, in which each client observes a sequence of examples {{ {xx²) (l(")) } Je.......' j= M,
and but does not share personalized data with others. There is a central server that coordinates the clients by sharing personalized models or gradients (Konečný et al.
2016 Kairouz et al.) 2021 Zeng cct al. 2023a bj. OMS-DecD captures some real-world applications where the data may be collected by sensors on M different remote devices or mobile phones [Li et al. 2020 Patel et al. 2023 Kwon ctt al. 2023], or a local device can not store all of data due to low storage and thus it is necessary to store the data on more local devices (Slavakis et al. 2014 Bouboulis et al. 2018 OMS-Dech can
be defined by minimizing the following regret,
M T
T ΣΣ e (x(2) (x+") 21 j=1
M
ΣΣS 1=1
(1L
(2) (x )
min 1 t C..... Tu M
- min FET:
where 1( E U is the hypothesis adopted by the j-th client at the 1-th round. Solving OMS-
DeeD must achieve two goals: GI minimizing the regret, and G2 providing privacy protection.
A trivial approach is to use a noncooperative algorithm that independently runs a copy of an OMS algorithm on the M clients. It naturally provides strong privacy protection, that is, it achieves G2, but suffers regret bound that increases linearly with M. It is unknown whether it achieves GI. Another approach is federated learning which is framework of cooperative learning with privacy protection and is provably effective in stochastic convex optimization [McMaaan et al. 2017 Woodworth et al. 2020b Wang al. 202I Reddi et al.) 202T). It is natural ask:
Question 1. Whether collaboration is effective for OMS-DeclD
The question reveals the hardness of OMS-DecD and is helpful to understand the limitations of federated learning. Previous work studied a special instance of OMS-DecD called distributed online multi-kernel learning (OMKL) where F; a reproducing kernel Hilbert space (RKHS), and proposed three federated OMKL algorithms including vM-KOFL, eM-KOFL (Hong and Chae [022] and POF-MKL Ghari and Shen 2022). ). The three algorithms also suffer regret bounds that increase linearly with M, and thus can not answer the question. If K = 1. then OMS- DesDDDe is equivalent to
distributed online learning [Mitra et al. [202]] Kwon et al., 2023 Patel al. 2023). A noncooperative algorithm that independently runs online gradient descent (OGD) on each client achieves the two
goals simultaneously (Patel et al. 2023 Collaboration is unnecessary in the case of K 1.
In summary, previous work can not answer the question well. On one hand, previous work can not answer the question in the case of K > 1. On the other hand, in the case of K 1, previous work has ans wered the question only using the statistical property of algorithms, i.e., the worst-case regret, but omitted the computational property which is very important for real-world applications.
1.1 Main Results
In this paper, we will answer the question from a new perspective of computational constraints on the problem (Section 5.5). Our main results are as follows.
(1) An upper bound on the regret. We propose a federated algorithm, FOMD-OMS, and prove an upper bound on the regret (Theorem 2. Besides, if Fi ..... FF......Fr Fx are RKHSs, then our algorithm improves the regret bounds of FOP-MKL [Ghari and Shen 2022 and eM-KOFL (Hong and
Chae 2022
at a smaller computational and communication cost. Table summarizes the results.
(2) Lower bounds on the regret. We separately prove lower bound on the regret of any (possibly cooperative) algorithm and any noncooperative algorithm (Theorem 3
(3) A new perspective of computational constraints for Question I By the upper bound and lower bounds, conclude that (i) collaboration is unnecessary when there are no computational constraints on clients, thereby generalizing the result for distributed online learning, i.c., K = 1; (ii) collaboration necessary if the computational cost on each client limited o(K) where irrelevant parameters are omitted. Our results clarify the unnecessary nature of collaboration in previous federated algorithms for distributed OMKL.

---

1.2 Technical Challenges
There are two main technical challenges on designing a federated online model selection algorithm.
The first challenge lies in obtaining high-probabiliity regret bounds that adapt the complexity of individual hypothesis space, a fundamental problem in online model selection [Foster et al. (017]. While acquiring expected regret bounds that adapt the complexity of individual hypothesis spaces is straightforward, the crux is to derive high-probability bounds from expected bounds. To this end, we introduce new Bernstein's 's inequality for martingale (Lemma which might be of independent interest.
The second challenge involves achieving per-round communication cost of oKK). To tackle this challenge, we propose two techniques: (i) decoupling model selection and prediction; (ii) an algorithmic framework, named FOMD-NN-LUU, which might be of independent interest. Specifically, when clients execute model selection, server must broadcast an aggregated probability distribution, denoted by p TR to clients, naturally incurring a O(K) download cost. Our algorithm conducts model selection on server and makes predictions on clients, thereby eliminating the need to broadcast the aggregated probability distribution clients. Additionally, if use the local updating approach [Mitra et al. 2021 Patel et al. 2023]. then server must broadcast K aggregated models to clients, also resulting in a O(K) download cost |Ghari and Shen 2022]. By utilizing FOMD-No-LU, our algorithm only broadcasts the selected models to clients and can achieve a o(K) download cost.
2 Related work
Previous work has studied the necessity of collaboration for distributed bandit convex optimization (Patel et al. 2023), where federated algorithmic framework named FEDPOSGD was proposed. Although the regret bounds of FEDPOSGD are smaller than some noncooperative algorithms, there not lower bound on the regret of any noncooperative algorithm (Patel et al.) 2023]. Moreover, the regret analysis of FEDPOSGD is based on the analysis for federated online gradient descent that not applicable to our algorithm, FOMD-OMS The regret analysis of FOMD-OMS requires the analysis for federated online mirror descent with negative entropy regularizer.
Our work is also different from federated bandits, such as federated K K-armed bandits (Wang et al. 2020) and federated linear contextual bandits (Huang et al.] 2021]. For OMS-DecD, we do not assume that the examples (x{"), ))( 1,.... T. on each client independent and identically distributed (i.i.d).. In contrast, in both federated K-armed bandits or federated linear contextual bandits, the rewards must be i.i.d., thereby making collaboration effective. This is similar to the approach used in federated stochastic optimization. However, this may not hold true for OMS-DedD, Therefore, it is distinctive problem for OMS-DecID to study whether collaboration is effective.
3 Problem Setting
Notations Let X = fx | co} be an instance space, y {y R ly| < oo} be an output space, and ((x, y.) (e)) be a sequence of examples, where [T] = {1, "I....,T), T). X, E X and ye y. Let S = {$1 s2....} be a finite set, Uni(S) be the uniform distribution over the elements in S and str] be the abbreviation of the sequence $1, $2,..,,777777 Denote by P[A]] the probability that an event A occurs, a A 6 min(a, b). V max(a, bj and log(a) = (a).
Let v-x()) Ω + R, I E [T' be a sequence of time-variant strongly convex regularizers defined on a domain Ω. The Bregman divergence denoted by Dv, (t. :). associated with v-((-) is defined by
Yu, Ω,
(u, (u) vv( (V). v).
3.1 Online Model Selection (OMS)
Let F -Fi, FR} contain K hypothesis spaces where
F (f(x) - TT(((() (x(x) < U.).
(I)
3

---

Let Fi. E F be the optimal but unknown hypothesis space for a given {(x,, 31) Be)t)) OMS can be defined as follows: generating a sequence of hypotheses f(r] that minimizes the following regret,
T
T
Vi [K], Rc
Σ e(ft(x)).)) - min FEF
(f(())) Be),
where Sa UK The optimal hypothesis space F5+ must contain good hypothesis and has low complexity [Foster et al. 2017 2019]. and is defined by
Σ ((I(x)). o (VT. t=1
Fi- arg min RIFF
min REFL
where C, measures the complexity of Fi, such as U2 and di.
OMS is more challenge than online learning, since we not only learn the optimal hypothesis space, but also learn the optimal hypothesis in the space. Next we give some examples of OMS. Tuning). Let F; consist of linear functions of the form
Example 1 (Online
= -f(x)) = (w, (w,x),I1 1|w||2 S Ui},
where U, a regularization parameter. Let (U,, [K] U, UUZ.... Uk} The hypothesis spaces are nested, i.e,, Fi
FK. C. The optimal regularization parameter U.+ E U corresponds to the optimal hypothesis space Fz- E F.
Example 2 (Online Kernel Selection (Shen et al. 2019 Li and Liao 2022). Let ka(:))) Rd Rd R be positive semidefinite kernel function, and 0i R
Rd. be the associated feature mapping.
Fi is the RKHS associated with Kü i.e.,
F, (x((xx)= = (W, (x(x)) |wlla U.}.
The optimal kernel function Kiz- E (K1,..., [K corresponds to the optimal RKHS Fi- E F.
Example 3 (Online Pre-trained Classifier Selection (Karimi et al., 2021)). Generally, Fi can be well-trained machine learning model. Let F contain K pre-trained classifiers. For new instance Xt. we select a (combinational) pre-trained classifier and make a prediction. The selection of a pre-trained classifier has an important implication in practical scenarios.
3.2
Online Model Selection with Decentralized Data (OMS-DecD)
We formally define round t, each client observes an instance x and selects hypothesis f(²) E U [M].
as follows. Assuming that there are M clients and a server. At any
Then clients output predictions (F()) (x } The goal is to minimize the following regret
(
M
Vi E [K]. Reg (F.)
(xP)))))
min JEF
M e (F(xP)))
where ()) is the label or true output. Each client can not share personalized data with others, but can share personalized models gradients via the central server.
4 FOMD-No-LU
In this section, we propose a federated algorithmic framework, FOMD-No-LU (Federated Online Mirror Descent without Local Updating) for online collaboration.
Let Q be convex and bounded decision set. At any round f, each client E [M] selects a decision
( E Ω and then observes loss function (-)( : + R. The client computes the loss 2.50 (uf²) and an estimator of the gradient denoted by zt (or the gradient denoted by gf (5)), To reduce the communication cost, we adopt the intermittent communication (IC) protocol [Woodworth et al. 202T] where clients communicate with server every N rounds. Assuming that T N x where N, R e Σ, the IC protocol limits the rounds of communication to R.

---

We divide [T] into R disjoint sub-intervals denoted by (T, -- in which
T, {(r 1) (r 1)NV + 2, 2.....,NN.
(2)
For any t E Tr, all clients always select the initial decision, i.c.,
Vj [M] Vt Tr, 4
(
(1-1)1
At the end of the -oundd, all of clients send & EieT. g [M] to server. Then server updates the decision within online mirror descent framework [Bbeeck and Cesa sssa-Biancii, 2012].
1 M
M
o6 )
gt
(4)
j=1
IET.
V Got1 2h (ū++1) = V, u. e (u,) Dt:
(5)
U++1 = arg min Dv, (u, i
(6)
( is called model averaging [McMahan et
2017 and shows the collaboration among clients.
Finally, server may broadcast U to all clients. Let the initial decision u = u for all j E [M],
then must be u! u, for all [7]. Thus clients do transmit 4ن") server. The pseudo-code of FOMD-No-LU is shown in Algorithm]] 1
4.1 Regret Bound
Theorem 1. Let & = (N,2N, RN} where N T and R E [T]. Assuming that (.)())) (-),
nt
t e [T.jE E [M], are corvex loss functions. Let St. = -V viyi (u(2) and g.5)) be an estimator of (5) At any round E &, let q and r441 be two auxiliary decisions defined as follows, 9t
M
V ya (o((+11) V un (u.)) - Σ
9t
ti = V Ve
2
95
M
M
Then FOMD-No-LU guarantees that,
T 11) (u. - (10
Da: (ue, re+1)
Vv E Ω
ΣΣ
Σ
(v, - D (v,
NM
2
1E8
Dv. (1c,
9c+1)
(() 9t
( 9t
M
It is intriguing that the regret bound comprises two components: the first part, E,, cannot be reduced by collaboration, while the second part. Eg. highlights the benefits of collaboration. E₁ is the regret induced by exact gradients, while Eg is the regret induced by estimated gradients and shows how collaboration controls the regret. It worth mentioning that Theorem givee general regret bound, from which various types of regret bounds can be readily derived by instantiating the decision set Ω and the regularizer v-e(-). For instance,
= J, where F, follows Example ( = 2
1 ||v
and E (1) [111) (1llg [|3, then FOMD-No-LU becomes federated online descent descent. It is easy to give a OMM (1 Y)) expected regret from Theorem Besides, N increases the regret and shows the trade-off between communication cost and regret bound.
Theorem requires a novel analysis on how the bias of estimators, i.c., Σn 11 of 11. is controlled by cooperation. To this end, we introduce two virtual decisions q and r that are updated by 2 ビj=1
(2) -gr and 2 A oi
(5)
j== Wr respectively. Previous federated online mirror descent Thus its analysis is different from ours.
exact gradients gr j E [M] Mitra et al. 2021
())
5

---

Algorithm FFOMD-N--LU
Algorithm 2 FOMD-ONN OMS (i = =)
Require: f2
Require: T.J. {U;, A,, [K]]
Ensure: u1 .j [M
Ensure: f10 = 0. Pt. [K].j [M]
1: for r = 1-,2..... R do
for t 1,2, ...,, do
2: for = (r- 1)N
NN do for ,.... M parallel do
for j .....,
3:
3:
Server samples 0 following
4:
Client selects (r-1)N-1 Ω
4:
Server broadcasts f() 0 client
5:
Client ohserves loss function (-) Client computes estimated gradient g
end for
6: for j 1,..., in parallel do
6:
Client outputs f1.) (x())
7:
end for
8:
if
= then
8:
Client computes V0) 9.3 4.. 1..iie00 0
Clients transmit N EEET. g. Server computes u Following (4)
[M]
10:
9:
Client transmits V. i0
10: end for
11:
Server may broadcast u++1
12: end if
11: Server computes Pe+1 following
B
12: Server computes W [K] following 9
13:
end for
14:
end for
13: end for
4.2 Comparison with Previous Work
In fact, FOMD-No-LU adopts the batching technique [Dekel al. 2011]. that it divides [T] into R sub-intervals and executes (3) during each sub-intervals. The batching technique (also known as mini-batch) has been used in the multi-armed bandit problem [Arora et al. [012 and distributed stochastic convex optimization (Karimireddy et al.) 2020 Woodworth et al. 2020a]..
We use the
batching technique for the first time distributed online learning.
FOMD-No-L.U is different from FedOMD (federated online mirror descent) MMitra et al. 2021 (i)
FedOMD only transmits exact gradients, while FOMD-No-LU can transmit estimated gradients. Thus the regret bound of FedOMD did not contain E2 in Theorem [ (ii) FedOMD uses local updating, such local OGD (Patel et al. 2023] and local SGD [MeMahan al., 2017 Reddi al. 202T]
Thus FedOMD induces client drift, i.e., u f u, Besides, if we use FedOMD to design a federated online model selection algorithm, then the download cost is in O(MK) bits.
A Federated Algorithm for OMS-DecD
In this section, we just consider the case R T, that is, there is no communication constraints. Due to space constraints, we have deferred the algorithm and result of R < ''' to the appendix.
At high level, our algorithm comprises two components both of which are critical for achieving communication cost in o (K)): (i) decoupling model selection and online prediction; (ii) collaboratively updating decisions within the framework of FOMD-No-LU.
5.1 Decoupling Model Selection and Prediction
Model Selection on Server At any round server maintains hypotheses (fl)) Fi and probability distribution P (i) over the K hypotheses for all [M]. The model selection process aims to select hypothesis from { and then predicts the output of x("). An intuitive idea is that, for each j E [M], the client samples hypothesis following p. However, such an approach requires that server broadeasts p (f) to clients, and will cause a download cost in O(K).
The sampling operation (or model selection process) can he executed on server. Specifically, server just broadcasts the selected hypotheses, and thus saves the communication cost. For each j [M], server selects J E [2, K] hypotheses denoted by a E [J] where Ar,a E [K]. For simplicity, let
0.") (A........ }. We instantiate u, Pr in FOMD-No-LU, Then FOMD-No-LU ensures

---

1 Pr Pr for all j E [M]. We sample A,, ... Ar,J in order and follow 7
{
Ar,1 Pt,
Ataa ~ Uni([K] \ {A,,,... (A..,)..,,AA,-11)))) a [].
Server samples 0 for all j E [M] and thus must independently execute ( M times which only pays an additional computational cost O(M log K). The factor log K arises from the process of sampling a number from [1.... K.. Server only sends f E [J] to the j-th client. It is worth
mentioning that server does not send p.. The total download cost is O(En Eá (dA.,a +og K)).
If / is independent of K, then the download cost is only O(M log K).
Prediction on Clients For each j E [M], the j-th client receives f(i) E [J], and uses St.Ae, to output a prediction, i.e.,
0 - (xx2) = -( L.A,, Rd (xA,)())))) (xx())
where we assume that f(. is parameterized by (1) e,z E Rdd (see 11). After observing the true output
2 the client suffers a loss ((()) A (x( ()
It is worth mentioning that the other J - 1 hypotheses At., 2 2 are just used to obtain more information on the loss function. We will explain more in the following subsection. Thus do not cumulate the loss 8 (((()) (x(
(6]
(x("), ).
(()) 2 2.
5.2 Online Collaboration Updating
Updating sampling probabilities For each j E [M]] let c (c.. 2, where oi
E (x()) (,), vt is the loss of fl. E [K]. The j-th client will send C. í E o.0), to server.
Since (1)
C,2 & o.2) can not be observed, is necessary to construct an estimated loss vector of
(al)) (cl.)...., (KK)
(1) 20 where 260 P I Too i E [K]. It is easy to prove that E,
and E, (c))) 5 (c.
(c( where E+1- E [0 [1-1] Thus sampling At..
reduces the variance of the estimators which is equivalent to obtain more information on the true loss.
Server aggregates a(!) j E [M] and updates p. following 4
6
Let A be the - (K--1)ddimmnte dimensiionl
(K-1)-diel
simplex, Ax and ())) a(i) Then the server executes
M
V pups the (p++1) =V (p.)
M
j=1
P++1 arg min Dos Pr+1),
DEAx
K Σ
C, Pt Inp.
V. (p)
T
where (p) is the weighted negative entropy regularizer [Bubeck et al. 2017 7t 0 time- variant learning rate and C > 0 satisfies that max, 4,1 broadcast P++1-
(1)
< C. is obvious that server does not
Updating hypotheses For each j E [M] and i e [K], let v! = v mn (( ox))))) vl"))
Since ())
t & 0. are unknown, it is necessary to construct an estimator of the gradient, denoted
by V ( f. Pl kEO for all j [M], i E [K]. Clients send (V())
via)
1, o J.j j [M] to
server. Then server aggregates ( [K]], [M] and updates the hypotheses following

---

6 For each E [K], let Q Fi and 9.
Server executes D
M
V W Ve, Wer =V we We, (W.))
4
i= 1,,,.,, K,
M
j=1
We+1i = arg min D Des,, (w, We+1,s);
wEP:
(w)((w)
[w]] |w]
2
where (w) is the Euclidean regularizer and Aτ, is time-variant learning rate.
We name this algorithm FOMD-OMS (FOMD-No-LU for OMS-DeclD and show it in Algorithm 2
5.3 Regret bounds
To obtain high-probabiliin regret bounds that adapt to the complexity of individual hypothesis space, we establish new Bernstein's is inequality for martingale.
Lemma 1. Let X1y..., Xn be a bounded martingale difference sequence w.r.t. the filtration H and with [xx] S a. Let Zr = Ei-1 Xx. be the associated martingale, Denote the sum of the conditional variances by M =E [ and 2 2 a constant. Then for any constant a > with probability at least 1 - 2[log B1ō,
Hx-11 S v, where v E [0, B] is a random variable
2a
1
2
1 +2 8
max Zi
<
3
Note that e is a random variable in Lemma 1 while it is a constant in standard Bernstein's inequality for martingale (see Lemma A.8 (Cesa-Bianchi and Lugosi 2006)). Lemma i derived from the standard Bernstein's 's inequality along with the well-known peeling technique Bartlett et al. 2005).
Assumption 1. For each [K], there is a constant by such that [x)x(x)] S b; where dx(-) is
defined in (T)
Lemma 2. Under Assumption 1 for each [K], there are two constants C 0, G. that depend on U; or by such that maxe,j 4,3 S C. and maxt,j [V 2,5 l2 I Gi- T. Under Assumption [ax Ci. Assuming thut E(.,-) is convex and K 2 J 2. Let gK.J
Theorem Let
7 denote by Am = [rgming[[]] Cj and C
K-J
J-I'
VK
E Ams P1,1
1-
+
and Vi Ams Pi, = VKT
[Aml
VT
VKT
Vnn (KT)
1
U:
Vt [T], T)
A1.3
2/ +
2KW 31
2gK.J"
2G (1 g
(kk vI)
With probability at least - A log() + (KT())
5, the regret of FOMD-OMS satisfies:
Vi E Reg = M MM / /1+
9K.J
+ B1a 9K. 9K. 1 T B 9K.J in 3
M
where U,
BA, MC + U.G, and = U,G, VCC.
Both C2 and G; depend on U; or by (see Lemma 2 Let OU,,G C.). Thus E, measures the complexity of F,. Then our regret bound adapts to CC, where C = max C, while previous regret bounds depend on C Ghari and Shen 2022 Hong and Chac 2022). that is, they can not adapt to the complexity of individual hypothesis space. C. & C, then our regret bound is much better.
The regret bound in Theorem is also called multi-scale regret bound [Bubeck et al. 2017]. However, previous regret analysis can not yield probabiioyyyllityy multi-scale bound. The reason is the lack of the new Bernstein's 's inequality for martingale (Lemma []. If we use the new Freedman's 's inequality for martingale [Lee et al.] 2020), then high-probability bound can still be obtained, but worse than the bound in Theorem 2 by factor of order (pooly(nn
8

---

5.4 Time Complexity and Communication Complexity Analysis
For each j E [M]. the j-th client makes prediction and computes gradients in time oiiiooe d.). Server samples O .j E [M], aggregates gradients and updates global models. The per-round time complexity on server O(Ei=1 Eieoga dN + Σx de + JM log K).
M
Upload At any round E [T]. the j-th client transmits ci, ta E 0 and the corresponding indexes to server. requires oo d; + 1) floating- paating-point numbers and J integers. we use 32 bits represent a float, and use log K bits to represent an integer in [K]. Each client transmits (32J (52J(E ( d; + 1) + Jog K) bits to server.
v!
Download Server broadcasts Wx,i E RRd i E and the corresponding indexes clients. The total download cost (22M]C d4 + +1 MJ log K) bits.
5.5 Answers Question
Before discussing Question D we give two lower bounds on the regret.
Theorem 3 (Lower Bounds). Assuming that 5 S K & min(d, T). For each i E [K], let F; (f(() e, x} and D; = [minxex J,(x), maxxex [i(x),, where e, is the standard basis vector in Rd. Denote by sup the supremum over all examples.
(i) There are computational constraints on clients. Let l(u, v) lu- yl- The regret of any algorithm for OMS-DecD satisfies: lim-->oc sup ma Regn(FF) 2 0.25. K:
(ii) The per-round time complexity each client is limited O(J). Let l(u, v) 1- v.y. y. The regret of any, possibly randomized, noncooperative algorithm with outputs in Uselk Di for DMS-DecD satisfies: sup E|max;e [K] (e.)(FF)) 0.MMKTT- where the expectation is taken over the randomization of algorithm.
where
The assumption that the outputs of any noncooperative algorithm belong to U D; is natural, and be removed in the case of J 1. Next we define a noncooperative algorithm, NCO-OMS.
Definition (NCO-OMS). NCO-OMS independently samples O² following and executes
Vj [M], Vp =V p.oii (D! -c(),
2(6)
(1) arg min Dw, (p.1). DEAx
P++1
Twera We+1.) =V Wo (w(.)) -
W ( = arg min D (w, We+1,)); wEF,
141,
where the definitions of of) and v/5) t, follow FOMD-OMS.
is easy to prove the regret of NCO-OMS satisfies: with probability at least θ (M log((T)) -8. O(M
Vi E [K], (F =0
M
BL. / 9K.)) BB.T+BB..000
BI J In
1 8 BLa BLay/an, 9k,
gk. Tin In
where B = U,G: + Ciyy (T(/)) Br.2 = C + U,G, and B = U,G, + VCC. We leave the pseudo-code of NCO-OMS and the corresponding regret analysis in appendix.
Next we discuss Question T by considering two cases.
Case 1: There are no computational constraints on clients. Collaboration is unnecessary.
Let J = @(K) in FOMD-OMS and NCO-OMS. By Theorem 2 both FOMD-OMS and NCO-OMS enjoy O(MU,G,VT + MCI/TTI(HH TIT(TT) regret. By Theorem FOMD-OMS and NCO-OMS are nearly optimal in terms of the dependence on M and T. Thus collaboration is unnecessary.
Case 2: The per-round time complexity each client is limited to o(K). Collaboration is necessary.
Let o(K) in FOMD-OMS and Theorem 3 By Theorem 2 FOMD-OMS enjoys + MWT regret, which smaller than the lower bound on the regret of any noncooperative algorithm (see Theorem 3 Thus collaboration is necessary.

---

Table 1: Comparison with previous algorithms. D is the number of random features Recht 2007]. Time (s) the per-round time complexity on client.
Rahimi and
Algorithm
Regret bound
Time (s)
Download (bits)
cM-KOFL
Ô (CMVTIIA Ó (CMVKT
C.MT VD
O(DK)
O(DM log K)
POF-MKL
C.
O(DK)
O(DMK)
VD
FOMD-OMS
Ô (C.VTIIK++ VEEMAT
S.MT
O(D)
ODD log K)
VD
6
Application to Distributed OMKL
We will apply the proposed FOMD-OMS to special instance of OMS-DecD, known distributed OMKL, which F; is a RKHS. Then we contrast our results with those from earlier studies, highlighting the unnecessary nature of collaboration in prior federated algorithms.
Theorem 4. Let Fi be a RHKS for all i E [K] and R < T. With probability at least 1 e (T' log(R) +T (R))K 6, the regret of FOMD-OMS satisfies, Vi E [K].
Regn (Fi) 0
9K.J T M
Bok,
BRST VR
VMK..
UTG.MTY
+
VR
VD
where the notation Ö(:) hides polylogarithmic in 8-1 and D = follows
We defer the algorithm in appendix. Let R T and J 2. We compare FOMD-OMS with eMM-OFFL [Hong and Chae 2022 and POF-MKL. (Ghari and Shen 2022 [gives the results.
We observe that FOMD-OMS significantly improves the computational complexity of eM-KOFL and POF-MKL (by factor of O(K)) on each client. The per-round time complexity of the two algorithms is O(DK). Recalling the answer to Question (see Section 5.5) collaboration in eM-KOFL and POF-MKL unnecessary.
Next we compare the regret bound of the three algorithms. Recalling that C, < C. The regret bounds of cM-KOFL and POF-MKL can not adapt the complexity of individual hypothesis space. (i) The regret bound of FOMD-OMS is better than that of POF-MKL. in relation to its dependence on M and C. (ii) the case of K = e M In IInK), the regret bound of FOMD-OMS better than that
of eM-KOFL. (iii) In the case of K = Ω ( M In K). the regret bound of FOMD-OMS is worse than that of eM-KOFL. If K sufficiently large, the regret bound cM-KOFL is better than that of FOMD-OMS by factor of OVVK).
7 Conclusion
In this paper, have studied the necessity of collaboration for OMS-Decl from the perspective of computational constraints. We demonstrate that collaboration is unnecessary when there are no computational constrains clients, while becomes necessary if the time complexity each client limited to (K). Our work clarifies the unnecessary nature of collaboration in previous algorithms for the first time, gives conditions under which collaboration is necessary, and provides inspirations for studying the problem from constraints beyond computational constrains.
Acknowledgements
We thank anonymous reviewers their valuable comments and suggestions. This work was supported by the Major Key Project of PCL (No. 2022ZD0115301..
10

---

References
Raman Arora, Ofer Dekel, and Ambuj Tewari. Online bandit learning against an adaptive adversary: from regret to policy regret. In Proceedings of the 29th International Conference Machine Learning, pages 1503-1510, 2012.
Peter L. Bartlett, Stéphane Boucheron, and Gébor Lugosi. Model selection and error estimation. Machine Learning, 48(1):85-113, 2002.
Peter L.. Bartlett, Olivier Bousquet, and Shahar Mendelson. Local rademacher complexities. Annals of Statistics, 33(4)) 147--1377, 2005.
Pantelis Bouboulis, Symeon Chouvardas, and Sergios Theodoridis. Online distributed learning over networks in RKH spaces using random fourier features. IEEE Transactions on Signal Processing, (6(7):1920-1933) 2018.
Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, New York, NY, 2004.
Sébastien Bubeck and Nicold BisscBiinchh.. Regret analysis of stochastic and nonstochastic multi- armed bandit problems. Foundations and Trends in Machine Learning, 5(1):1-122, 2012.
Sébastien Bubeck, Nikhil R. Devanur, Zhiyi Huang, and Rad Niazadeh. Online auctions and multi- scale online learning. In Proceedings of the 2017 ACM Conference on Economics and Computation, pages 497-514, 2017.
Nicolò Cesa-Bianche Bianchi and Gábor Lugosi. Prediction, Learning, and Games. Cambridge University Press. New York, NY. 2006.
Ofer Dekel, Ran
Ohad Shamir, and Lin Xiao. Optimal distributed online prediction. In Proceedings of the 28th International Conference on Machine Learning, pages 713-720, 2011 1.
Dylan J Foster, Satyen Kale, Mehryar Mohri, and Karthik Sridharan. Parameter-fiee online learning via model selection. Advances in Neural Information Processing Systems, 04-6022-60322 2017.
Dylan J Foster, Akshay Krishnamurthy, and Haipeng Luo. Model selection for contextual bandits. Advances in Neural Information Processing Systems, 32: 12:14741-14755 2019.
Pouya M. Ghari and Yanning Shen. Personalized online federated learning with multiple kernels. Advances in Neural Information Processing Systems, 55:33316-33329 2022.
Avishek Ghosh and Sayak Ray Chowdhury. Model selection in reinforcement learning with general function approximations. In Proceedings of the European Conference on Machine Learning and Knowledge Discovery in Databases, pages 148-164, 2022.
Mark A. Hall, Eibe Frank, Geoffrey Holmes, Bernhard Pfahringer, Peter Reutemann, and Ian H. Witten. The WEKA data mining software: an update. SIGKDD Explorations, 11(1):10-18, 2009.
Songnam Hong and Jeongmin Chae. Communicaiion-effccinnn randomized algorithm for multi-kernel online federated learning. IEEE Trunsactions on Pattern Analysis and Machine Intelligence, 44 (12):9872-9886 2022.
Ruiquan Huang, Weiqiang Wu, Jing Yang, and Cong Shen. Federated linear contextual bandits. Advances in Neural Information Processing Systems, 34:27057-27068. 2021.
Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista A. Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael G. L. D'Olivera, Hubert Eichner, Salim El Rouayheb, David Evans. Josh Gardner, Zachary Garrett, Adrià Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaid Harchaoui, Chaoyang He. Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi, Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konečný, Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo, Tancrède Lepoint, Yang Liu, Prateek Mittal, Mehryar 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, Pranceth 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-210, 2021.
Mohammad Reza Karimi, Nezihe Merve Gürel, Bojan Karlas, Johannes Rausch, Ce Zhang, and Andreas Krause. Online active model selection for pre-trained classifiers. In Proceedings of the 24th International Conference on Artificial Intelligence and Statistics, pages 307-315, 2021.
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank J. Reddi, Sebastian U. Stich, and Ananda Theertha Suresh. SCAFFOLD: stochastic controlled averaging for federated learning. In Proceedings of the 37th International Conference on Machine Learning, pages 5132-5143, 2020.
Jakub Konečný, Brendan McMahan, Felix Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. CoRR, atXIv:161000549222,, 2016.
Dohyeok Kwon, Jonghwan Park, and Songnam Hong. Tighter regret analysis and optimization of online federated learning. IEEE Transactions Pattern Analysis and Machine Intelligence, 45 (12):15772-15789, 2023.
Chung- Wei Lee, Haipeng Luo, Chen- Yu Wei, and Mengxiao Zhang. Bias no more: high-probability data-dependent regret bounds for adversarial bandits and mdps. Advances in Neural Information Processing Systems, 13:15222-15533, 2020.
Junfan Li and Shizhong Liao. Improved regret bounds for online kemel selection under bandit feedback. In Proceedings of the European Conference on Machine Learning and Knowledge Discovery in Databases, pages 333-348, 2022.
Junfan Li and Shizhong Liao. Improved regret bounds for online kernel selection under bandit feedback. CoRR, MtXiv:2303.05013 2023.
Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Challenges, methods, and future directions. IEEE Signal Processing Magazine, 37(3):00-60, 2020.
Zhu Li, Jean-Francois Ton, Dino Oglic, and Dino Sejdinovic. Towards unified analysis of random Fourier features, In Proceedings of the 36th International Conference on Machine Learning, pages 2019.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agüera y Arcas. Communication-efficcennn learning of deep networks from decentralized data. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, pages 1273-1282, 2017
Tom M. Mitchell. Machine Learning. McGraw-Hill Science, New York, NY. 1997.
Aritra Mitra, Hamed Hassani, and George J. Pappas. Online federated learning. In Proceedings of the 60th IEEE Conference on Decision and Control, pages 4083-4090, 2021.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning (second edition). MIT Press, Cambridge, MA, 2018.
Aldo Pacchiano, My Phan, Yasin Abbasi- Yadkori, Anup Rao, Julian Zimmert, Tor Lattimore, and Csaba Szepesvári. Model selection in contextual stochastic bandit problems. Advances Neural Information Processing Systems, 33:10328-10337 2020.
Kumar Kshitij Patel, Lingxiao Wang, Aadirupa Saha, and Nathan Srebro. Federated online and bandit convex optimization. In Proceedings of the 40th International Conference on Machine Learning, pages 27439-27460, 2023.
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. Advances in Neural Information Processing Systems, 20: 10:1177-1184, 2007.
Ali Rahimi and Benjamin Recht. Weighted sums of random kitchen sinks: Replacing minimization with randomization in learning. Advances in Newral Information Processing Systems, 21:1313- 1320, 2008
12

---

Sashank J. Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and Hugh Brendan McMahan. Adaptive federated optimization. In Proceedings of the 9th International Conference on Learning Representations, 2021.
Yevgeny Seldin, Peter L. Bartlett, Koby Crammer, and Yasin Abbasi-Yadkori Prediction with limited advice and multiarmed bandits with paid observations. In Proceedings of the 31st International Conference on Machine Learning, pages 280-287, 2014.
Yanning Shen, Tianyi Chen, and Georgios B. Giannakis. Random Ceature-based online
learning in environments with unknown dynamics. Journal of Machine Learning Research, 20 (22):1-36, 2019.
Konstantinos Slavakis, Georgios B. Giannakis, and Gonzalo Mateos. Modeling and optimization for big data analytics: (statistical) learning tools for our era of data deluge. IEEE Signal Processing Magazine, 31(5):18-33 18-11, 2014.
Roman Vershynin. High-dimensional probability: An introduction with applications in data science. Cambridge University Press, New York, NY, 2018.
Jianyu Wang, Zachary Charles, Zheng Xu, Gauri Joshi, H. Brendan McMahan, Blaise Agüera y Arcas, Maruan AheShvvivat, Galen Andrew, Salman Avestimehr, Katharine Daly, Deepesh Data, Suhas N. Diggavi, Hubert Eichner, Advait Gadhikar, Zachary Garrett, Antonious M. Girgis, Filip Hanzely, Andrew Hard, Chaoyang He, Samuel Horváth, Zhouyuan Huo, Alex Ingerman, Martin Jaggi, Tara Javidi, Peter Kairouz, Satyen Kale, Sai Praneeth Karimireddy, Jakub Konečný, Sanmi Koyejo, Tian Li, Luyang Liu, Mehryar Mohri, Hang Qi. Sashank Reddi, Peter Richtárik. Karan Singhal, Virginia Smith, Mahdi Soltanolkotabi, Weikang Song, Ananda Theertha Suresh, Sebastian U. Stich, Ameet Talwalkar, Hongyi Wang. Blake E. Woodworth, Shanshan Wu, Felix X. Yu, Honglin Yuan, Manzil Zaheer, Mi Zhang, Tong Zhang, Chunxiang Zheng, Chen Zhu, and Wennan Zhu. A field guide to federated optimization. CoRR, Siss22107.06911 2021.
Yuanhao Wang, Jiachen Hu, Xiaoyu Chen, and Liwei Wang. Distributed bandit learning: Near- optimal regret with efficient communication. In Proceedings of the 8th International Conference on Learning Representations, 2020.
Blake E. Woodworth, Kumar Kshitij Patel, and Nati Srebro. Minibatch vs local SGD for heteroge- neous distributed learning. Advances in Neural Information Processing Systems, 33:6281-6292 2020a.
Blake E. Woodworth, Kumar Kshitij Patel, Sebastian U. Stich, Zhen Dai, Brian Bullins, H. Brendan McMahan, Ohad Shamir, and Nathan Srebro. Is local SGD better than minibatch sgd? In Proceedings of the 37th International Conference on Machine Learning, pages 10334-10343, 2020b.
Blake F. Woodworth, Brian Bullins, Ohad Shamir, and Nathan Srebro. The min-max complexity of distributed stochastic convex optimization with intermittent communication. In Proceedings of the 34th Annual Conference on Learning Theorr, pages 4386-4437 2021.
Dun Zeng, Siqi Liang, Xiangjing Hu, Hui Wang. and Zenglin Xu. Fedlab: A flexible federated learning framework. Journal of Machine Learning Research, 24 2023a.
Dun Zeng, Zenglin Xu, Yu Pan, Xu Luo, Qifan Wang, and Xiaoying Tang. Enhanced federated opti- mization: Adaptive unbiased client sampling with reduced variance. CoRR, arXiv:23 10.02698....
2023b. URL httpt:ttt///ett /tttps://arxiii org/ 2b1/ 026998
Xiao Zhang and Shizhong Liao. Online kernel selection via incremental sketched kernel alignment. In Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, pages 3118-3124, 2018
Xiao Zhang, Shizhong Liao, Jun Xu, and Ji-Rong Wen. Regret bounds for online kernel selection in continuous kernel space. In Proceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence, pages 10931-10938. 2021.
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the Twentieth International Conference on Machine Learning, pages 928-936, 2003.
13

---

A Limitations
The main limitation of this work lies in the first lower bound in Theorem 3 that holds in the case of T - oc. Although this lower bound nearly matches our upper bound asymptotically and is enough to answer Question | it is desired establish a con-asymptotical lower bound, that is, the lower bound holds for any value of T.
B Broader Impact
This work can be potentially applied to distributed online prediction tasks. aim to address fundamental problem whether collaboration among clients is necessary and under what conditions collaboration is necessary. A predictable economic benefit of our work is to give a guidance on the usage of federated learning and save unnecessary communication overhead.
Our work can also instruct the machine learning engineers to tune the hyper-paramest of online learning algorithms. Thus our work can alleviate the burden of machine learning engineers and improve the utility of online leaning algorithms industrial applications.
C Experiments
In this section, we aim verify the following three goals which main results.
GI Collaboration is unnecessary if we allow the computational cost on each client to be O(K). We set R T and J = K in FOMD-OMS. In this case, the per-round running time each client is O(K). We aim to verify that FOMD-OMS enjoys similar prediction performance with the noncooperative algorithm, NCO-OMS with J K (see Definition I
G2 Collaboration is necessary if we limit the computational cost each client to o(K). We set R = T and J 2 in FOMD-OMS. In this case, the per-round running time on each client is O1). We aim to verify that FOMD-OME enjoys better prediction performance than NCO-OMS with = 2.
G3 FOMDOOOOOOO O-MM--MSS improves the regret bounds of algorithms for distributed OMKL.
FOMD-OOF OMM with R = ' and J = 2 enjoys similar prediction performance with eM-KOFF [Hong and Chae 2022]. , and enjoys better prediction performance than POF-MKL Ghari and Shen 2022 at smaller computational cost on each client.
Although there
baseline algorithms, such as vM-KOFL (Hong and Chae 2022 pM- KOFL Hong and Chae 2022] and OFSKL [Ghari and Shen 2022 we do not compare with the three algorithms since they do not perform as well as eM-KOFL and POF-MKL.
C.1 Experimental setting
We will execute three experiments and each one verifies a goal. For simplicity, we do not measure the actual communication cost and use serial implementation simulate the distributed implementation.
To verify G1 and G2, we use the instance of online model selection given in Example The first experiment verifies G1. We construct 10 nested hypothesis spaces (i.e., K = 10) as follows
Vi E [10], F. = {x(x = (w, x), ||w||2 S U.}.
where U = To We set R = and = in FOMD-OMS. Since J K, we have 0
1.
[K]
and TP 0( = 1. The learning rates 1t, At,s, i E [K] of FOMD-OMS follow Theorem For
NCO-OMS, we set J K and set the learning rate ne, Ae,s, i e [K] following Theorem in which M 1, i.c.,
In (KT)
U 2G.VE
Vt E [2], 1/
A
2VT
We use the square loss function {(f(x),)) = (f(x) - 2) For both FOMD-OMS and NCO-OMS, tune G; (U, + 11 ) 21, 4, 6,8, 8, 10) and set C. = (U, 2
14

---

Table Basic information of datasets.
Dataset
Number of Instances
Number of features
bank
8,190
32
ailerons
13,750
40
calhousing
14,000
8
elevators
16,590
Torwwardware
28,170
96
Twitter
50,000
77
Year
51,630
90
Slice
53,500
384
The second experiment verifies G2. We set == T and in FOMD-OMS, The learning rates of FOMD-OMS also follow Theorem
2 For NCO-OMS, also set J 2 and the learning rate Mt, Ae,i, E [K] following Theorem in which M = 1, i.e.,
VIn (KT)
1
U.
A 2G: - 1)- ((K 2)2 Vt) Similar to the first experiment, tune G, (U; + 1) 21, 6, 10) and set C, (U; + 1)
Vt E [T). T) 2V(K 1) 2(K 2)
The third experiment verifies G3. We consider online kernel selection (as known as online multi- kernel learning) which is instance of online model selection given in Example 2 Gaussian kernel with 8 different kernel widths (i.e., K 8),
We select the
||x v 2
Vi [8]. (x, v) exp
o. 2
2'-2
and construct the corresponding hypothesis space F; and H4, following (1) in which we set Uj U and D; = D for all E [K] and tune U E {1, 2, 4). Note that U, is same for all E [K]. We replace the initial distribution P1 in Theorem 2 with a uniform distribution ( ..... )). We set D) 100 for FOMD-OM -MM, KOFL and POF-MK D is the number of random features. We set R T. J J= and C U + in FOMD-OMS Thus the per-round time complexity on each client is O(D) and the per-round communication cost is O(MD M log K). There are three hyper-paramen parameters in
eM-KOFL, i.e., f/g. !it and X. T/ is the global learning rate, Yy is the local learning rate and À is a regularization parameter. There are 2M + hhyper-paramette m, A in which M/m plays the same role with J in FOMD-OMS. 7/g the global learning rate, ?) is the local learning rate, E, is called exploration rate and À is regularization parameter. Since J J= in FOMD-OMS. we can set m = M/2 for FOMD-OMS, Following the original paper Ghari and 1. For fair comparison, we change the learning rates of FOMD-OMS.
in POF-MKL, i.e., '/4 f/j Ej. E [M].
Shen 2022), we set cM-KOFL and POF-MKL. Following the parameter setting CM-KOFL [Hong and Chae 2022 we tune ng. Mr 7, {0.1, 0.5, 1,4, 8, 16) and À (0.1. 0.001, 0.0001) for eM-KOFL and MKL. For FOMD-OMS, we also tune M/, Xe,5 E f0.1, 0.5, 1, 16).
For all of the three experiments, we set 10 clients, i.e., M = 10. We use 8 regression datasets shown 2 from WEKA F Hall et al. 2009) and UCI machine learning repository [ and rescale the target variables and features of all datasets to fit in [0.1] and [-1,1] respectively. For each dataset, we randomly divide it into subsets and each subset simulates the data on client. We randomly permutate the instances in the datasets 10 times and report the average results. All algorithms are implemented with R on a Windows machine with 2.8 GHz Core(TM) 17-1165G7 CPU
We use the square loss function and define the mean squared error (MSE) of all algorithms, i.e.,
MSE-
MT ΣΣ
( x
(1)
We record the mean of MSE over 10 random experiments, and the standard deviation of the mean of MSE. We also record the mean of of the total running time on each client, and the standard deviation of the mean of running time.
https://aaikato
httpa://archive. ics. uei. dedd.eddmml/inde.. php
Thee code of algorithms is available at D0tl////o.//o/////////o////ooDD0 http://OLELLL-TTTTOO---------- git
15

---

Table 3: Comparison with the noncooperative algorithm. A is the difference of MSE between
NCO-OMS and FOMD-OMS. aE-b = a x 10 100". . 0,6 > 0.
elevator
bank
Algorithm
MSEx10
Time (s)
A
MSEx 10
Time (s)
A
NCO-OMS
0.991 + 0.002 K 1.31 + 0.10
2.158 + 0.022 K
0.88 1 0.05
1E-4
1E-3
FOMD-OMS
0.980 + 0.005
K 0.65
+ 0.08
2.020 0.005
K
0.33 + 0.08
NCO-OMS
1.168 + 0.005
0.58 + 0.04
2.321 0.021
2
0.39 + 0.05
1E-3
2E-3
FOMD-OMS
1.024 + 0.002
2 0.14 4: 0.04
2.118 + 0.003
2
0.08 + 0.03
TomsH Hardware
Twitter
Algorithm
MSEx 102
Time (s)
A
MSEx10² J
Time (s)
A
NCO-OMS
0.090 + 0.004
K 3.02 + 0.29
0.017 + 0.000 K
5.11
+ 0.24
1E-4
FOMD-OMS
0.083 + 0.008
K
1.48
+ 0.28
0.017 0.000
K
2.07
+ 0.07
NCO-OMS
0
2
1.11
+ 0.07
0.018 + 0.000
K
2.24
1 0.25
4E-4
1E-5
FOMD-OMS
1.107 0.003
0.44 + 0.09
0.017 0.000
2
0.51 + 0.05
ailerons
calhousing
Algorithm
MSEx10 J Time (8)
A
MSEx10
Time (s)
NCO-OMS
19.506 + 0.033
K 1.41 0.04
10.166 0.029 K
1.07 + 0.05
3E-4
3E-4
FOMD-OME
19.480 + 0.046
K
0.74
0.08
10.136 + 0.012
K
0.43 + 0.05
NCO-OMS
20.323 + 0.036
2
0.65
0.05
10.372 + 0.021
2
0.53
0.04
5E-3
1E-3
FOMD-OMS
19.820 + 0.032
0.20
+ 0.04
10.227 0.014
2
0.12
+ 0.05
Algorithm
year
Slice
MSEx10
Time (s)
A
MSEx10
Time (s)
NCO-OMS
20.322 + 0.040
K 5.94 + 0.25
13.097
0.009
K
10.40
+ 0.94
2E-3
1E-3
FOMD-OMS
20.096 + 0.045
K
2.25
+ 0.20
12.964
+ 0.007
K
4.12 + 0.18
NCO-OMS
24.334 = 0.021
2.95
0.63
13.364
0.012
2
3.60
+ 0.23
1E-2
3E-3
FOMD-OMS
22.705 + 0.040
0.59 + 0.09
13.038
0.009
2
1.41 + 0.12
C.2 Results of the First and the Second Experiment
We summary the experimental results of the first and the second experiments in Table 3
In Table 3 A defined the difference of MSE between NCO-OM and FOMD-OMS, Thus A shows whether collaboration improves the prediction performance of the noncooperative algorithm.
Times (s) records the total running time on all clients.
We first consider the case J = K in which the per-round time complexity on each client is O(K). It is obvious that the MSE of NCO-OMS is similar with that of FOMD-OMS. Although there four datasets on which FOMD-OMS performs better than NCO-OMS, such as the elevator, bank, Year and Slice datsets, the improvement is very limited. Beside, the value of A is very small. Thus collaboration does not significantly improve the prediction performance of the noncooperative algorithm. The results verify the first goal GI.
Next we consider the case obvious that FOMD-OME performs better than NCO-OMS all datasets. Besides, the value of A in the case of J = 2 much larger than that the case of J = K, such as the elevators, ailerons, ailerons and Year datasets. Thus collaboration indeed improves the prediction performance of the noncooperative algorithm. The results verify the second goal G2.
in which the per-round time complexity on each client is O(1). It is
Finally compare the running time of all algorithms. It is obvious that FOMD-OMS with J 2 runs faster than the other algorithms. The results coincide with our theoretical analysis. NCO-OMS runs slower than FOMD-OMS. The reason is that NCO-OMS must solve the sampling probability Pt using an additional binary search on each client (see Section G.I). In other words, NCO-OMS must execute binary search M times at each round. FOMD-OMS only executes binary search server at each round. The improvement on the computational cost is benefit from decoupling model selection and prediction.
C.3 Results of the Third Experiment
We summary the experimental results of the third experiment in Table
16

---

Table Comparison with the state-of-the-a2 algorithms.
elevator
bank
Algorithm
MSE
J
Time (s)
MSE
Time (s)
cMM-KOFL
0.00292
0.00013
2.67
0.05
0.01942 = 0.00066
1.41 = 0.06
POF-MKL
0.00806 + 0.00026
3.12 + 0.14
0.02292 + 0.00036
1.59 + 0.13
FOMD-OMS
0.00318 0.00021
2
0.52 0.08
0.01917 + 0.00110
0.27 = 0.06
Harwwardware
Twitter
Algorithm
MSE J
Time (s)
MSE
Time (s)
cMM-KOFL
0.00048
0.00003
5.88 0.69
0.00007 = 0.00000
9,60 = 0.77
POF-MKL
0.00188 = 0.00004
6.60 - 0.93
0.00020 = 0.00001
2
10.44 = 0.54
FOMD-OMS
0.00059 0.00003 2
1.46 0.12
0.00010 + 0.00001
2.23 + 0.18
ailerons
calhousing MSE
Algorithm
MSE J
Time (s)
Time (s)
eMM-KOFL
0.00370 0.00011
2.40 = 0.19
0.02242 = 0.00043
2.28 = 0.06
POF-MKL
0.01335 = 0.00046
2.66 + 0.12
0.05248 = 0.00197
2.68 = 0.08
FOMD-OMS
0.00429 0.00021 2
0.48 0.04
0.02373 + 0.00126
2
0.39 + 0.07
Algorithm
year
Slice
MSE J
Time (s)
MSE
Time (s)
eMM-KOFL
0.01481 0.00108
9.60 0.51
0.05781 + 0.00230
12.74 + 0.95
POF-MKL
0.01896 = 0.00036
10.73 + 0.29
0.08675 = 0.00402
14.22 = 0.54
FOMD-OME OMS
0.01534 = 0.00121
2
2.26 + 0.10
0.05698 + 0.00480
2
4.82 = 0.21
We first compare FOMD-ON with eM-KOFL. As whole, the MSE of the two algorithms is similar. the TomsHardware, Twitter and ailerons datasets, eM-KOFL. enjoys slightly better prediction performance than FOMD-OMS. However, the running time of eM-KOFL. is much larger than that of FOMD-OMS. The results coincide with the theoretical observations that FOMD-OMS enjoys similar regret bound with eM-KOFL much smaller computational cost the clients.
Next compare FOMD-OMS with POF-MKL. Both the MSE and running time of FOMD-OMS are much smaller than that of POF-MKL. The results coincide with the theoretical observations that FOMD OMS enjoys a smaller regret bound than POF-MKL a much smaller computational cost on the clients.
Thus the results in Table verifies the third goal G3.
Finally, we explain that why POF-MKL, performs worse than FOMD-OMS. There are three reasons.
(1) POF-MKL does federated learning to learn global probability distribution denoted by Pt. but learns personalized probability distribution denoted by Pt.j on each client. Thus POF-MKL converges the best kernel function at lower rate.
(2) POF-MKL uniformly samples two kernel functions and then learns two global hypotheses, while FOMD-OMS uses р, sample a kernel function and learns global hypothesis. Thus POF-MKL can learn a better global hypothesis.
(3) On each client, POF-MKL executes model selection and combines the predictions of K hypothe- ses using Pt.. Thus the time complexity is in O (DK). FOMD-OME executes model selection server, and only uses the sampled hypothesis to make prediction. Thus the time complexity on each client O(D).
D A Federated Algorithm for OMS-DecD with Communication Constraints
Let R < T. Clients communicate with server every N rounds. At the r-th communication, clients (1) transmit \ ΣieT, V Eier, q, heof to server at the last round in T,. Then server updates
sampling probabilities and hypotheses. We give the pseudo-code in Algorithm
17

---

Algorithm 3 FOMD-OMS (R < T)
Require: U.T. J.
Ensure: 11] Pr,s, i j E [M]
1: for 11, do for ET do
2:
3:
if == (r 1)N + then
for j = 1,..., M do
5:
Server samples 0 following
6:
Server transmits 16 E 0 to the j-th client
7:
end for end if
9:
for j = I...., M in parallel do
Output (()) , (xl")
10:
11:
for i 0 do
Computing vil and .0) end for end for
12:
13:
14:
15:
ift == rN then
16:
Clients transmit ( Eier, V.
N Eier, a. (e) server
17:
Server computes Pt+11 following
18:
Server computes We+1,s; i [K] following 9
19:
end if
20:
end for
21:
end for
Theorem 5. Let R T. For any t [R), ler
VK
E Am, Pı,
+
and
Vi
Ams Pı, =
[Aml
VR
VRR
VKR'
VIn (KR)
1
U;
VI E [R], Th
d
2 (1+
2K. M
R
2gk.J
2G (1+ 2x,2) ) (okc,) vt)
Under the condition of Theorem the regret of FOMD-OMS satisfies: Vi E [K].
2 with probability at least 1-0 ( AM R.) + 1 log(K (K KR/KKR/ R/M))
Regn (FF) - M MB
JK.J M
+ T B..,,
In +
B.&T VR V
MMKK In 1
VR
R
The regret bound depends on O( (²) mance and the communication cost.
Thus FOMD-OMS explicitly balances the prediction perfor-
Proof. If FOMD-OMS runs on sequence examples with length T R, then Theorem givess with probability at least θ (lg((R) + Log(CKR/M) 8,
Regp (Fi) 0 MB (1+
9K.J
R BL29K. In B 9k MRln 1 M
According to Theorem I the regret bound of FOMD-OMS with R < T satisfies, with probability at least 1 θ [ M log(C(R) n log(CKR/M)) 8.
Rog =0
NMM..1 (1+
9K.J M
) R NB
8 + NB 9K. 9R,n
=0
T
MB..
1+
9K.J
+ T
B229K.J
T Br3 JK In
VR
M
R
VR
which concludes the proof.
18

---

E Proof of Theorem I
We first state technical lemma.
Lemma 3 (Boyd and Vandenberghe (2004), D. Assuming that (5 : X + R is convex and differential
function, and is a convex domain. Let f = jegmin (f). Then it must be
Ag E X, (vu(f), - 20
Lemma gives the first-order optimality condition.
Proof of Theorem 7
We first consider the case R = T.
The main idea is to give lower bound and upper bound (ūt, u141 v), respectively, Next give an upper bound.
(r U141 v)
=( [(V - Vi u++1 v)
= <(,,,br(uy)) - Vu (el(uet U++1 vv + (V (Vut,) ( - V Vaens (ee(()))), ur+1 v)
=Do, (v, uz) - Du. (v, Us+1) - Dos (u++1, uz) - (V Pv. (u++1, ac+1): v - u++1)
<Day (v, u.) - Da, (v, U141) Day (ue+1; Up).
The last inequality comes from Lemma
Then we give lower bound.
(et u++1
v)
M
1
(60h)
It: u v})
(i)
u+11 v)
M
j=1
M
(3) (1)
-v)
1
(3)
(3)
9t u
9t
U1+1
Ut
+
9t
9t
U
M
M
M
E2
where u.
u, Next we analyze E and E2.
To analyze E,, we introduce an auxiliary variable r4+1 defined as follows
2
Ve (e(++1) = Vu.ve(u))
M 9t
Σ
j=1
Then have
M
E
(
uu+1
u
2
M
j=1
Vuu (w:) - Vr (e((1)1)) u441 - -u:)
2
(P (ou41 - D (u ux) - (u.
2
1
2 (D u,) + (u,,
Before analyzing Eg, we also introduce an auxiliary variable qi+1 defined as follows
V qeen (1(q++1) V., (u.)
Σ g
9r
(1)
j=1
19

---

Now we can analyze Eg.
We have
M
M
2
(f)
(3)
(J)
(1)
E2
9t 96 11+1 - U
9t
96
ur
M
M
1=1
j=1
1
Vu, (ue) - 2/ u141 u1) + +3
1 (Do(ust 90+1) Du( ue) (p(())9tt1)) + +3s
2 2 2
(uL- u.) + De (u, 9(+1)) + Es.
Combining the lower bound and upper bound gives
( (1) v M Si u
j=1
+ 1 (ue, SDe (v, u.) Das (v, u1+1) Ea + D (++))
Using the convexity of 110), that is, 10 (u 16' (v) s (16" pp -v). we further obtain
1 (ul 11 (v))
M
SD (v. u.) - Date (v, u(+1) 1 ( which concludes the proof.
(u,, 9411) + (p(s, +
Now we consider the case R < T. Recalling that & 2N,
2N, 3N ..... RN) and
T, ((r 1)N + 2,.., r= r= I=...... R.
For any batch T,, r .,... R, we define new loss function 7 (-) at the end of this batch,
Vj E MM. Yu
Σ (n).
N
TET.
During each batch, our algorithmic framework does not change the decision, i.e..
Vj E [M], LE Tr, (i)
u 1NN+++
Thus the regret can be decomposed as follows,
M Σ (1 - (M)
Σ
1 (2 (4
[ET,
M
N
(10) (u - -12(())
M
N
tET.
N
ΣΣ
(u 5 (ー -
M
Now can use FOMI-No-LU with R = T to the new loss functions (T.)) (..:...., use Theorem
((dd) Jr=1..., R. and
(oo obtain
T M
1. (u, ()) (v)) - Σ
(v. - Dev (v, u1+1) +
2 Da, (u, | +
1
NM
338
M
Σ
De, (ug, +
1
9r
91 .u v).
(
M
330
335 j=1
20

---

which concludes the proof.
F Proof of Lemma
Lemma (Bernstein's inequality for martingale). Let Xi...., Xn be bounded martingale differ- ence sequence w.r.t the filtration H. (Ht)isksn and with [Xxl S Let Ze - Xx be the associated martingale. Denote the sum of the conditional variances by
Σ
Σ E
He- Sv.
Then for all constants a, 0, with probability at least 1 - 8,
2 a In
1 2v 5" V
max
Z,
+
Note that e must be a constant. 2006
Lemma derived from Lemma A.8 in (Cesa-Bianchi and Lugosi
Proof. Let U E [0, B be random variable and B 2 2 is a constant. We use the well-known peeling
technique [Bartlett et al. 2005 We divide the interval [0, B3 as follows
[og B1
[0, B C ( [log B
U
(2'-1.21)
llggB1+ B1+1
First, we consider the case v > 2 [log B1, Let
2 In
1
2 a
2
1
2 B
6 6= (=
P vln
+
2
2 1 log B In
In
+
3
5
5
8
We decompose the random event as follows,
I
max I....
Ze > c, Σ
0,0
2- flo
IP
max Ze
U. e, Σ
lox B1
2 <US 2¹
ビ=
llg B1+1
1Sn
[lo B1
P
max Ze > e, 12 20, 2- < <0<2 tSn
log B +1
[lng
Σ
P
max Z
aal1 5 2
1
2 In
1
52
2--1 <05 2
isn
[lg #1++
[log B1
a In 1 + 12
1
P
max Z,
5
2
8r
2
<
<こ 2
e.
2-1
tsn
[lo B1+1
<2 log B75.
in which we use Lemma for each sub-event.
Then we consider the case v 2- B1 < B. Lemma
yields, with probability at least - 8,
max Z, - an + V II....,
Nog n In
1
2 In
1
8
B
Combining the two cases, with probability at least
2 2og B|
2a In
2
1
max
Z, 5
+
2
In
t 1.
3
8
which concludes the proof.
21

---

G Properties of Online Mirror Descent (OMD)
G.1 OMD with the weighted negative entropy regularizer
Let Ω = Ax and (p) K C. Pi In ps- d1
Then we have
C, (Imp++1) +), 1), (p)
C₁
1
1/2i
The Bregman divergence associated with the negative entropy regularizer
Di, (p.q)
C
pi In
4: Pi
(10)
?e
Denote by C,
M7 Σラ= ()) Recalling that the OMD is defined as follows,
Vp41 (P++1) Vp. (pt) - Ct2 P++1 = arg min Dv. (P. P.+1)-
płåx
Substituting into the gradient of 4/,, the mirror updating can be simplified.
Vi E [K], P = Pt. exp
(-c,
C,
Now we use the Lagrangian multiplier method to solve the projection associated with Bregman divergence.
K In
K B.p
((p, A)
C
Pt
Ps + Pu+1, -pi pt.
+ +
Σ
P)
P1+1,
i=1
i=1
1=1
The KKT conditions are
0L
Inp, + 1 - In Pc+1, -
C₁
+ x 33 =0,
0p:
17p
0L
K
Σ Ps 1--1) 0,
0X
Bp, O.
Let Pc+1. X and ( be the optimal solution. By the KKT conditions, we have
C; (-
nx(A² - -3;)
Pt-1; -P+115 exp
K
3
K
ne(A*
B + Ct,i)
P - exp
Pt. exp
=1,
C₁
C
1=1
87
07=0,
in which the last equality comes from P1+1, 0. The reason is that by the fact P1, for all
i [K]. we can iteratively prove that Pt,; > 0 and Pc+ > 0, satisfying the condition under which
3 = 0. Then obtain the solution Pr+1. i.e.
Th(A + Cc,i))
Vi E [K],
P1+11 = Pt, exp
(11)
C2
Next prove that X* can be found by the binary search.
X 2 0, then Σk Pt. exp +o())
EK Pi, 1.
C.
If X* < - max; Cz.i. then Σ Pt.i exp
> Σ Pt,i 2 1.
C,
Thus must be max, Ct,; S X < O. For any
\1
2 A2 2
max, Ct.i we can obtain
K
mi(d + C..))
TTeed2 (-na(Ae Cx,1) C₁
Σ
Pt.i - exp
Pt,s exp
C2
+(x+) C;
Thus Σ Pt.i exp
is non-increasing w.r.t. X*
We can use the binary search to find X².
22

---

G.2 OMD with the Euclidean regularizer
Let Fi and (e)(w)
||w]] 122-
Then we have
2
1 V (r,(()
1 de,
1
Vw Rd, Vw)),((W)
Der,(w,v
1/w
v112.
A
2A1
Recalling that the OMD is defined as follows,
V W Vt (We+1.)
V Vw.. (We,s) Vess Wo+1 arg min D Dec,s (w, Wo+1,) WeFF
The mirror updating is follows,
Ve,i Vi E [K], W1+1,1 =W1 da,5
U²
W1+1 min
|
W1+1.
Thus OMD with the Euclidean regularizer is online gradient descent Zinkevich 2003).
H Proof of Lemma 2
Recalling that ( E(5()) (x (x))), ).()) ()), in which 1 (xx) = ( (x(2)) S U,b.
Since ( is uniformly bounded for all j E [M] and E [T], there is a constant C₁ that depends on Ug and 6, such that cii S SCe.
Recalling that v ((F ). (x Since E( (x(x) ), () can be upper bounded
by C, and (x l|l2 b;, there is constant G; that depends on U, and b, such that | l|2 G,
I Proof of Theorem 2
The regret w.r.t. any fE F; can be decomposed as follows.
M
(122,, (xP2)
(F(xP)) )
M
(x42
(xf2 + + (x49)
(1(x)))))))]
T M
T
M
(1l) (x())))))
(r(x9)).
C.Ar,
Next we separately give an upper bound on E4 and Es.
L.1 Analyzing E4
We start with Lemmal and instantiate some notations.
Ω Ak.
==vE Ak.
34 E [T],
9 ct
())
9t
20 =()
g: = c,2
(5) = Pt u. =
(1)
(2(wx)
(1)
(1)
1[(v)= (
pr:
23

---

Lemma I gives, Av E Ak.
T M
(
-v)
Pi
M
j=
D (v. Dus (v. +
1
Σ
Dvh (Pr. 9-+1 +
1 Σ
Dar (P) (12)
t=
1=1
t=1
M
c
P . -v-
(5)
M
Recalling that
M
-0))
5
Ve Vo((:)) = v, - Σ
9t
9t
(13)
M
1=1
Vrn (e(((1))) = uv, (1
2
9t
(2)
(14)
M
In we redefine Q = AK and (p)) = Σイ= G. p. In p.. and in we redefine ! = Ax and E/=
4 (p)
2C p; In p;. Using the results in Section G.1 i=l ni
we can obtain
E [K], 91+1, PP,,iexp
C2
8
M
2
2,1
(1)
j=1
(15)
M
2
(f)
TE+1i exp
20, 22,
Čt.i =
M
C,
j=1
It can be verified that σ,, [-20 2 Ci) and 6,, [0, 2C:)
Recalling the definition of learning rate 77, in Theorem We can obtain
Mohe C,
2 - and
>
-1.
20;
Next we use T0 and 15) to analyze the following two Bregman divergences.
T
Des (p4,
1
20
Pt.s In
Pt.
+ T Pt,s
11t
T(+1
1=1
1=1
1=1
1
Pr,mpes 22,
) Pr.s
20
+ Pt,s exp
7
20,
T
K
Pr,sihees 20,
nca.
(nees
)
)²
2)
20,
+ Pt
+
Pt.s
11
20
20%
2
2 M
PLA
2C
M Ø=1
M
K
1
M1
M
J=1
i=1
24

---

and
Σ
De. 9(+1)
Σ
1
C2
Pt,s In
Pt. + qu+1.3 Pt.s)
(=1
(=1
T
i=1
9++1,
1
Σ
C2
Pr,
+ Pt,i cxp
pe,3
111
C₁
Ci
T
M
Pt.i
1
(1)
4
11c
C
M
ct.
1=1
1=1
f=1
in where we use the fact exp(-2) S - x + x² for all 2 1.
Substituting the two upper bounds into 12 gives
1 Av E AK,
M
54.1
2
T
1 M
Σ
(v. - Dvv (v, Pc+1))
+2 Σ
17
Pt.i
(66)
9
C₁
M j=1
31,2
E,,3
T
M
K
T
M
(1())
C: Pt - v)
(5)
PL.c 1.
Ci
M
[=1
j=
24.4
Bounding 2,2
We define a random variable X₃ as follows,
(f) ! X, G.A.. - (c
Let H, = (o " N. ...,,
Then we have H -y] = 0 and |X| < C where C = max, C.. Thus Xirj is bounded martingale difference sequence w.r.t. the filtration Hir]. The sum of condition variance satisfies
(t
T SC.
Σ
H
Σ
10) (de
> 1=1
(dPPpp .p. CrT
The upper bound is random variable. Lemma I Iiillds, with probability at least 1 M Co)(C
E
M
()) vv
2CM
3
In
8
1 2,
CM
(
Pt
(1)
In
5'
1
j=
where the fail probability comes from the union-of-events,, and the lower order term M V omitted.
2
In
is
Bounding E4.2
According to 10). we have
K Σ
K
Vi
C
1
C C.PI,k
E.2 5 DD. (v. =
C;
U;
In
+ P1.: 1/
<
In
P1,
P1.
1
7
i=1
Am1
25

---

Bounding L13
We define a random variable X₁ as follows,
2
K
M M
<??)
k
M
X₁
Σ
Pe.
- B
Pt.i
Σ
C2
C'
M
2,5
j=1
1m1
j=1
It can be verified that E[X, = and condition variance.
X
K-J
|_CC. C. Next upper bound the sum of
J-1
2
M
S
Σ
E,
Σ
Pt.
Σ
42)
C2
M
1=1
27
T
K Σ
M Σ
1
E
Ptf
C.
M
t.a
4,3
1=1
i=1
j=1
-K J)2 T
M Σ
1)- Σ EE
Σ
Pt.i
M
j=1
1)= 1
ΣD
Σ
20
ai! 2
Pr.:Br
(J- (J-1)² M2
1=1
(K (K-J² JJS C.
T M
Σ>
(
(J - M2
t=1
(K- - J]3 CTT,
1)3
where we use the fact aQ
(
K-1 ( c
Lemma yields, with probability at least
1
1 1 1-lo((C2 (3
E4,3 Sn
9K.J M
c
( 6)
Pt
2CgK.J
3
In
2
gK.J M
T
(o .p.
In
8
1=
t=1
where 9K.J
K J-1
and the lower order term
C In I is omitted.
Bounding 44,4
We define a random variable X, as follows,
1 M
K
X,
Σ (
d.)) Pp: ---vv v)
Σ
(pt. vz)
(24) (6h2 42) -c4)
M Ø=1
26

---

(X is a bounded martingale difference sequence and [Xt] S IK We further have
Σ
EX
27
E1
Σ Pt, 0/)
(2l.)
c.i)
+
M
k
)
E+
Σ
Σ (pes 11) -c))
Σ
Pr.i - 12))
(0/7
M
1
Σ
Σ
E,
Σ (pG. 11) (0/) - 4.7)
M t=
M Σ
K
27
T
M
K
2
Σ
Σ Pt.
(0) - C23
-
(3)
2
Σ
Σ Ui
(0
M 1=1 j=1
M 1=1
M
2
E2
Σ
Pt.
(0) 0)
+
M
2
E2
Σ
-
i==1
t=1 1=
T M
T M
22
JK.J C.
ΣΣ
2
OK.J
c 2 3c
M
M
==
t=1 j=
KT
M
(1) where (c 20000 ct vv'vv)) Ei= ((()))
With probability at least 1 - loggoog(CC KT/M)
4,4 5
2C In 2/ 2
1
_ M
In
1
ct p!!
ΣΣ
c
c .v)
9
3
8
For simplicity, we introduce some new notations
M
T [r(v)=
T
To
9) ))
ΣΣ of v)..))
ir(v)
Σ
f=1
Combining all
Combining all gives, with probability at least 1 ((Kg(CKTTMM)- 5,
f--Ir(v) s M
-
In
1
+
Σ
K
CAPIA
- -G)+
Pi,5
k=1
(1+
_K.J
LT +
2MC
IK.J In x + +2/ok. C Lr 1n +
1
M
3
2MCgK.J
In x
1
+ 2 29K,J In 7 VClr+ irlv).
3
27

---

Rearranging terms gives
(1 (1- (1+ (1+ _K.J
)) LT
2n
gk.
C
in
1 δ
2 29k VLr
+ 2 2g
M
<Ir(V)+ +
M
C
Σ
K
CAPI.-
4MC
In 5
+2
29KK In VLr(()).
1
P1ş
3
Recalling that, the solution of the following inequality
av x 0, 0,6>
is x S a² +b+ a.b. Solving for Lr gives
2211 OK. C'In J 5 + +2 2 (2gg)
2 Jk C'In 3 + 2 Cln,
- (v(
+
(1 (1-n 17 (1 ))² 2
(1 (1+ 2x.1
[v(v) + M
+ +I CuPL. - C.)
K
4MCgk.J 1 + +2
+ 29k.J In 8 Vir(M)+
In
In 8
P1.
3
k=1
17 (1+ 9K
M
[vr(v)+
1- (1 9K.2
M C In Pi.
L. + +K CAPI, - C.) 4MCaK.
In + 2 2g In v LL((v)
3
9K.J 1)
M
Denote by A.. grgmin,g|g] Cj. Let the learning rate and initial distribution Pı satisfy
In (KT)
J 2(K J)
2/
K-J 1
(J-1)M4
K
P1,k
VT
Am
VKT
E Am, PLá = VKT .j # Am-
Then have
K
C,
CaPIA C.
P1,
<C,L(VKT) + C. CK (Aml)
(11-
LKVk VK
1
1
+ +mnn C. AAml.
- C.
VKT
VT
Am
VKT
OVK
SC,l((VTT) + VT
28

---

We further simplify Lr- - Lr()).
LT [T(v)
<64gk, In 3 + +1ll IK,
CTM M
C,ln(VKT) + CvK
4MCgKJJ
1 + 2 2g 8 V [[(( ④
VT
(C,ln(VTT)
CVK VT
+
4MCaK.2 3
In 1/ + +22; ( 2 in } VTM
21/ 11
9K.J M
C
1 < (64+ 99,, J C In + 1 MC,T
4
K-J
G.M
[+
T'n(KT)
v2
- 1)M
E1,
in which omit the lower order terms such as O(T+) and Ol O 9kr f))
Finally, using the upper bound on E1,1 gives, with probability at least - ( (M log(CT) log( (CT/K))) 6,
4
<hr (v) +
2CM 1
In
+ 2,
CM
M
c
( p! ( In
3
M
- -x +
In + 2
CM (V) + E4,s) In _
3
4 C.M /
K-J
5(64+ (64++3M) Ch ④ + 17 MCK, 5 V2
1+
Tin (KT)+
1J-M)
2M v CC.TIn 1 y'
where we omit O CME4, In !) which is a lower order term.
I.2 Analyzing Es We also start with Lemma
We just fixed i E F, We instantiate some notations.
V Fi, Ω == Fi, ( ((6 -000 (0) 9: == -
Vt E [T],
u.() = (!
u, = Wt
M((w)) e (1 (x (2))))
(x (.) 1d(v) (f(xx))
(1) ). (66))
Lemma ggives
1 T M
Vw W Fi,
ΣΣ
Σ
(e (1. - (s(x("))
M
1
DDen. (w) (w, wo. +
Σ
Dun,i (Wes 4++1)+
t=1
T M
Den. (We.
(
v(5) W. w
2
M
1=1
t=
29

---

where the Bregman divergence is
1 v122.
Darea (w, v)
||w
2
Besides,
1
and
44
can be instantiated as follows
Md
91+1 Ae,
2
())
v
M
T(+1 =W - Ae.
2
Mf
(
M
==1
Thus have: Vw Fi.
M
w
Will3
-
1|w
W
T
A
1 M
())
v
(1)
+
2d1,
M j=1
[=1
[=1
T
M
T
M
A,
M
M
(
1.3
We
w
1=1
j=1
1=1
j=1
5
2U?
+ 2G
Σ
Ar, +
Σ
A
( f,1
v f,1
W.
w
Xr,
M
M
S6,1
Next we separately give whihhh-gohhhee probabiiity upper bound on E,, and E1.2-
Bounding E
We define a random variable X₂ as follows,
M
V w. ww
X₂ =
M
X is bounded martingale difference sequence w.r.t. Hzg and [X,] S GgU, We further have
T
T
M
$1 = Σ A
I
v()) 1.5
S 4U? 9K.J M
M
j=l
The upper bound on the sum of conditional variance is constant. Lemma gives, with probability at least 1 - 6,
4G.U.KKJ
1 In 2G, _
_K.J T In M
Es,
8
Bounding E
Recalling that
U:
if g
2G, v (1 1+ JK. )
A
otherwise.
2G; / (
SK.d 74
)
30

---

It can be found that Az,5 S Case 1: T sk.. We decompose E,, follows,
Un G
sk.
1 M M
2
T
S
A
v(.)
Σ Σ
M
j=1
+1
j=1
S
E0,1,2
We separately analyze E and E, Let
1
(3) v
X, A1,
be
M
M
XIT a martingale difference sequence and satisfies |Xel S de,i PK.. G2 S Ik.. We further have
9k
M
S U.?.? 9k. 4M
E4
X
2
E2
v() 6,2
M
t,z
1=1
==1
T
SU?
_K.J 4M
(T - 9k.j)
9
With probability at least 1 - 26,
vi!) !
1
2JK.J
GRU
/ 2K.KJ
1
E
In
+
+.Uss
Thn
M
3
M
5
9K.J
G²
A1.
2 GrU
In j
+ G.U.V 2 9K..
T
In
1
M
3
M
6"
Combining with all results gives, with probability at leat 1 - 35,
3.
2U?
+ 2G, (1
9K.J M
gk
Σ
Xe.i +
Σ
T
de,i
+
2g
1 G.Ugln
M
NT,
t1
2
3G,U.
In
M
2U?
+ G.U./ |+
v1+
9K.J
9K.J + L
Jemskeuta Veal vtat) + G,KK,
AT
M
2T
T
1
3G,U.V
In
M.
8
S6U,G;
(1+
9K.J
1 T + 29k, 3G,U, )
2g JT M
In
1
M
8"
Case 2: T' < Jk. In this case, we do not decompose Es,1 and de, 2G. (1+ 2 )ok.
U,
With probability at least
1 8,
<
JK.J M
G2
T
G.U,
3
In 5
1
+ G.U.v
9K.J T In
2MM
5
t=l
31

---

Furthermore, with probability at least 1 - 28,
M 3s - + +2?
2
(1+
9K.J M
Σ
T
Ae, +
5
In + 4G.Ui
IK.J T 8
NT.
3
8
M
S5U,G
JK.J
M
9K.J
+
5gK.
J 1
In
4G,U,
9..J M
T
8
Combining the two cases gives, with probability least 1 (M 5)6.
M Es - GU;
1+
9K.J M
(T+9k.)) + 29.. 8 + 3G,U,V
2gK.J Tin
M
8"
L.3
Combining all
Combining the upper bounds on E. and Es gives an upper bound on the regret.
With probability least 1 θ (M (CT( log(CKT/MM)
T
M
ΣΣ< ==
(FrA.,,
)x
Σ (((x))))1))
<M
9K,J M
GU,G; (VT + 9k.J) + V2
Ci TT +
(64C + 3MC + 2U,Gi)gk, In (3V2G,U, - - 17VC0,)
2Mg 3
+ 2MC, Tin 3
Omitting the constant terms and lower order terms concludes the proof.
J Proof of Theorem 3
We first establish a technical lemma.
Lemma 5. Let Xi,..., XK be sequence of independent standard normal random variables. Let
ZK = max(Xi,.... xk) If K 2 5, then E[Zx] 2 vo 22 K.
Proof of Lemma Proposition 2.1.2 in Vershynin 2018 of standard normal distribution.
gives lower bound the tail probability
(-4²²
x
V > P
2 x]
exp
du
exp
2T
2
2T
x3
2
Then have
k
=B |i E X 26) P [K], X, 26 B(ZxVXX <pp.P <$
23 [K] X; 2 e)
(1 P |XX, <<)
k
I[ XX < E) .0
1=1
K
II
(1
PP
[X; 2 8])
.8
1=1
1
1
1
2
2
3
exp
2
32

---

Let = 22 K. If K
>
5, then we have
1
1
E²
k
1
k
2T
E
x3
exp
2
=
2
/2
K
In
1.5
K2
K
h²
Ve
Substituting into the lower bound of [[ concludes the proof.
J.1 Proof of the First Lower Bound
Proof. Let d K, IRd and V {0,1}. We use the absolute loss function (x((x)) (bs
If(x)) - Vel. Recalling that
F (f(x) = (e; (e;,
1,,,,...,
where e; is the standard basis vector in Rd. It is obvious that the time complexity of computing fi(x) xz is O(1). At each client j, let the selected hypothesis be f(f) and the prediction be
(( ()) Since there are computational constraints on each client, st (3) can be weighted combination of K predictions, i.e., f(² (x(())
Σ w. fxx(")) The time complexity of computing (x(( is O(K). We will follow the techniques used in the proof of Theorem 3.1 in Patel et al. (2023 and Theorem 3.7 in Cesa-Bianchh and Lugosi [2006).
(xt
Following the proof of Theorem 3.1 in Patel al. [2033] the adversary gives sequence of same examples for each client. To be specific, we define
(x() vi = (Xe, Bt),
t= 1,,,,.., T, j = L,
where x, (bc,,, b1,2, b,,,,..., ... b,, K, O, .,, 0) Rdd and by, b ... K, Ut is sequence of symmetric i..d. Bernoulli random variables, i.e., PP(y = Ply: 0]
At any round t, the minimax regret against the best hypothesis can be simplified as follows
inf (0
sup
max Rega (Fi)
(x P J.JEEEMM
KE(K]
sup 1 m (EL KE[K]
inf
max Reg Regn((F (F.)
M
M ((i(x)))
E 10 (.. (XE
inf
Σ
(1.
min KE(K
1=1
inf
( (xx)
Vel
M min
Σ lf((x.) -vel
( ( (20) (X
{E[K]
MT
[((xx) -vall
M
E
min KE[K]
2
(X
-M
E
max K
s(xx)) - -
22y+)
(XE.9)))E(TT
in which f((x,)= = be.5 is Bernoulli random variable and
ΣΣ -1
1 (xx) (xx)
MT
Vc
E
V1
(XET)
(E(T)
2
33

---

We further obtain
M
inf (4)) A TT (x w JE(
sup
max Rego(FF)) {E[K]
E ftM.Ei.E
max
Zz 04
KE[K]
M
max [E[K]
Zz,k
M [T)
1=1
where both (E/M,)))))) and (T))) are i.i.d. Rademacher random variables.
By Lemma A.1I in Cesa-Bianchi and Lugosi
2006].
we obtain
T
lim
E
max KE[K]
Σ
Z
E
max G3
7-000
VT
[E|K]
where GI,... GN independent standard normal random variables.
By Lemma we obtain
lim inf T- A f (x MP JEM
sup
max Regp (F)D((F)2
(F)) 222 (1-11) ve
1 (1 11-- 1.11
M MV22
(E[K]
which concludes the proof.
J.2 Proof of the Second Lower Bound
We mainly use the techniques in the proof Theorem in Seldin et al. (0014), but also require a new technique. The idea of our proof is to reduce the online model selection each client to multi-armed bandit problem with additional observations.
Proof. Now we prove the second lower bound in Theorem
Let d 2 K, S TR. and y E 1). We use linear loss function ((f(x)), 1- (x(). Recalling that
F (f(x) = x),, == 1,2, K.
is obvious that the time complexity of computing fx) z, is O()) Under the constraint that the time complexity on each client is limited to O(J), each client, any algorithm can only select J hypotheses and then output a prediction.
One of challenges is that the prediction may be a combination of J predictions. To be specific, for each client j [M]. (x(") Σico!n (xxf)( where of?) contains the index of selected J hypotheses by some algorithm. To address this challenge, we introduce a virtual strat- egy that randomly selects a hypothesis [/p) E (JAnaIJA JA,,a following the distribution
(w..Ar.: At..A....... Ar.)..)) where Ara E 0.00 I,.., J. Since the loss function is linear function, it is easy to prove that,
E e
). (0)) = =E( p1 (x(2)) :/2 (1. (x(
(x ). v())
(16)
where the expectation is taken over 11"h. Assuming that (x(")) 1 S C for all i 1, K. Lemma A.7 in Cesa- Bianchi and Lugosi (2006) gives, with probability at least 1 - 6,
Σ Tec (x(2) ( e (x(' (xx)). ). S-
T In
Note that we assume Wt, 2 O and Eieo!) Wt,i 1 for all t= 1,,,,, T. Recalling that Theorem assumes the outputs of algorithm belong to [min f((x). max,e(K))xeN f((x)]. If we.; < or Eioo! We > 1, we can still find a weight vector w/, 2 and Eieo,n w/, = 1, such that
(x++))
Σ wr.xf(((())) (EO
Σ w/ w(,ff(x(()) i
34

---

Then we sample 160) following (w/ W/ (AA Wy, (Wr,A,,1 At, Ac.)) with (W/,Ar,) W/, " Wy )
We
can
replace
Since the algorithm is non-cooperative, the total regret be decomposed into the summation of the regret on each client. With probability at least 1 Mò,
M
T
T (xxx))))x(²))
Vi E [ Rego(FF)
=
1 1. (1
(x)
Σ
(f(((x)))
E=1
(x(2x)) De
Σ (Ie(x())
(xP))))))))
(1 (xx(") (..66)))
Σ
(1% (x(2)
(x((x()).
T +CV
In
(17)
2
5
(P)
Note that if we take expectation w.r.t. the randomness of algorithm, then the additional term
CV In in 117 can be omitted following 16
If the prediction is not combination of J predictions, but just ((: (x(").
then we have
1500
Σ (I(x)))
Vi [K], RegD(Fi)
(18)
Rego (Pi)
Combining with the two cases, we just need to analyze Reg Regn(FF).
The adversary first uniformly samples same h E [K] for all clients, and then constructs {(x()) y))) as follows
X (br,1, br, 0, 0).
0), 111 ( 1, j 1, I,..,, M,
in which bi,a satisfies
1 1-p
1+
PA (br.i = 1]
Ps [br, = 0
i h.
2
PA [br, 1] +
1- P 2
PA [r. = 0]
Let E& and Px[ separately be the expectation and probability operator conditioned on is selected.
Then have
1+p
Pn]((f(xx).)) = 0 1 -
PA (x,(((x)),
i i h,
1 1-p 1) = = 1 p PA (((f) = 2
2
It is obvious that online model selection can be reduced to a K-armed bandit problem, in which f; is the i-th At each round f,, let r!3)) be the selected arm. Besides, any algorithm select another arms. Thus any algorithm can observe J losses. Let (,5)) be the set of the selected J arms. Note that {65 f0 for any I(6) [K].
35

---

Assuming that the algorithm is deterministic, that is, 0 is determined by {0 )イ=ر and the observed losses. Let Nr.- Σi= I ",00 Taking expectation w.r.t. (bc.1:..., De. ) yields
(32)).1 16
Σ ecCiON).))
EA
min
iE[K]
(xx). 1)
Σ (clo0)))))
2B,
min En (E(K]
T
=p- EA
+
=p. (1
(1 En (Nral)
Following the techniques in the proof of Theorem 2 in Seldin et al. (2014). we have
JT 2p² K P
En [NT.a]] < K +
KT
h=1
Recalling that T 2 2 5. Let p
VR SVJ.
We further have
T
T Σ E((H(())))))
E
Σ
(123
min EA, VE(K]
1
3
JT
2pT.
K
2
2º
K
20.1 VKT
(19)
VJ
For any deterministic algorithm, we can prove
sup
max RegD(FF)
(2 00 JEE
KE[K]
T
M
T
M ((f(x)).1)
(1l
2 sup (x..1).
min K
T
M
T e (f((x)))
(x0)
sup
M min (E[K]
(x..1).te77)
2 sup KE[K] (T.TE(TT
Eg
M Σ
Σ
T
( (g) (xx)).))
Σ E((AA(s))))) (E(K]
min
M
T
T
sup
EA (T)
Σ
(1 (x)()))))
min Eg &E[K] x. XE(T
(e(f(s)))))
KE(K]
M
T
E
EA
(G0 (xx)
min EA, KE]K]
(f((x)) 1)
K
j=1
EA
Σ
(10 (xx)) (2)))
min EA KE[K]
Σ e(f((z)))
K
20.1M
T,
K
36

---

Algorithm 4 NCO-OMS
Require: T. J. m. A [K]}
Ensure: ((0 = 0. p1,s, "9,,,EE [K].j E [M]
1: for 1- -........ do
2:
M f do
3: The client samples 0 following 7
The client outputs f(5) Ar. (x)
4:
5:
The client computes Jr.At.a (Xg (5) for all 2, ......JJ
((5)
6: The client computes 76) and ald for all E O.
7: The client computes P++1 and w (1)
(1)
241,0 E [K] following Definition
8: end for
9:
end for
where the last inequality comes from 19 Bianchi and Lugosi [2006), the lower bound of any randomized algorithm is same with that of any deterministic algorithm, i.e.,
As claimed in the proof of Theorem 6.11 in Cesa
sup (x ( ME(T))E((
E
max Reg (Fi)
KE[K]
sup
E
Σ
(1) 1500
(xx²)
min K
l (A(xP))))))
(x at (ET
1=1
t=1
KT
20.1M
VJ
in which the expectation is taken over the internal randomness of algorithm. Substituting into or (88
concludes the proof.
K
Regret Analysis of NCO-OMS
Algorithm gives the pseudo-code of NCO-OMS.
Following the definition of NCO-OMS and Algorithm 4 obvious that the regret bound of NCO-OMS each client is same with Theorem in which we set M 1. The regret bound on M clients is M times of that of a client. Thus we have Theorem
Theorem (Regret Bound of NCO-OMS), Let the learning rate 1), A and the initial distribution Pi be same for each client j E MM). The values of dea and pı follow Theorem 2 in which M With probability at least θ Mog(( (ogg))))
regret of NCO-OMS satisfies:
Vi E []], (e. =
B (1 (1+ 9K.)) T Br,2K., In + Bisy 9K 9..
where BA, U,Gi+C. Bi C+U,G; and B., U,Gi+ VCC, and C max; C,.
L Proof of Theorem 4
L.1 Algorithm
We give the pseudo-code Algorithm 5
To implement Algorithm 5 we require one more technique, i.e., the random features [Rahimi and Rechi 2007). We will use random features to construct an approximation of the implicity kernel mapping. The are two reasons. The first one is that we can avoid transferring the data itself and thus the privacy is protected. The second one that we can avoid the O(T) computational cost on the clients.
37

---

For any i E [K], we consider the kernel function (x v) that has an integral representation, i.e.
ff ((x VX, v. vex, X
<x v)
(20)
where pi: x
R is the eigenfunctions and (4(()) is a distribution function on r. Let pa(.) be the density function of pı()). We sample {w>} Pz (w) independently and compute
1 D
1 D
Rx v)
Σ
pi(x ())
For any f(x) = Jr (( (w). レ =Σ a(wj)ppixx wj). . It can be verified that BB[(()) fxx). Such an approximation scheme also defines an explicit feature mapping denoted by
We can approximate f(x) by f(x)
(x(x) = VD
wD))
For each K i [K], we define two hypothesis spaces as follows
[Rahimi and Recht 2008 Li and Liao 2022
F = f(x) = / ()) [[((w)] s Ji).
D
H. =
f(x) = Σ (x,))
U D |ay1 -
(21)
5=1
U
f(x) = w w (xx) == VD ap) E ERD, <R,,1ay1 S
D
in which F; is exact the hypothesis space defined in T It can be verified that [w| < U. Let W; = {w ERP ||w |/w 100 I -.). }. We replace P
with (22).
M
V (eo(ee1),) =
60) 1,2
i 1 K,
M
J=1
Wi+1i arg min D Del, (w, Wc+1.)) wEW,
(22)
(w) 2Àx.s
|//
L.2 Regret Analysis
first give an assumption and a technique lemma.
Assumption Li al (2019). D. For any E [K], if, satisfies (20). then there is a bounded constant b, such that, Vx X,
[P: w) < b;.
Under Assumption 2 we have [x() < U,b; for any f E H., and f f F, It is worth mentioning that Assumption holds then Assumption [ holds with the same 6,.
Lemma 6. For any i E [K], let F; and follow 21
With probability at least - 8, Vf E F.
there is f E HI; such that lf(x) - f(x)) <
Ub.
2n }.
D
The lemma is adopted from Lemma 5 in [Li and Liao 2023
Thus we omit the proof.
Now begin to prove Theorem
38

---

Algorithm 5 FOMD-OMS for Distributed OMKL
Require: U.T. R. J.
Ensure: 11.7 50 P1,s,
[K].j E [M]
I: for r = =,,,....., do
2: for E T. do
3:
if = (r I)N + then
4:
for j 1, ...... M do
5:
Server samples 0 following
6:
Server transmits Wi,s E 0, to the j-th client end for end if
7:
9:
for j = I..... M in parallel do for 0 do
10:
Computing (x.)))
12:
end for Outputting WT..,, &Ar, (xx and receiving yt" for of5) do
13:
15:
Computing ( and C,2 end for
(5)
16:
17:
end for
18:
if ===-0 rN then
19:
()) Clients transmit ( ELET, Vir Pe. Ever, t. leo server
20:
Server computes P.+1 following
21:
Server computes We+1,s; E [K] following
22:
end if
23:
end for
24:
end for
Proof of Theorem
The regret w.r.t. any f F; can be decomposed as follows.
M T
M (xP)) - Σee (f(x?)),
5=1
M
(x - (11) (. + + (F12((( (x(2), (f(x))))
(xc
(1g
e (F((()))))) (f(x("))
Regg (Hl,) + E
Reg H. is the regret that we run FOMD-OKS with hypothesis spaces (HL f HI, satisfies
Lemma In other words, Eg is induced by the approximation error that we use f to approximate f.
Reg H. has been given by Theorem 5 Next analyze Eg.
39

---

Using the convexity of E(.,) -), with probability at least 1 - TMO
M de (((x")) )
(f(x)" - f(x{2))
B6
ff(x("))
de ),
- -
d )
MT S9.bUU-
2
VD
SG, 21n 1
MT
VD
((()))))))))))))
Under Assumption there is constant 9i such that comes from the definiioo of Lipschitz constant (see Lemma 2 Combining the upper bounds on Regp (HH,, and Es concludes the proof.
S 9r. The last inequality
40

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We have clearly stated our main results, technical contributions and scope in the abstract and introduction. The main results are also supported by our theoretical and experimental results.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We have discussed the limitations of this work in appendix (Section
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-specification. asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
41

---

Answer: [Yes]
Justification: We have give all assumptions in the main paper. Due to the limited space, we do not include proof sketches in the main paper, but give complete and correct proof for each theoretical result (including lemma and theorem) in appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the suppiemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We have clearly state the experimental setting and datasets, and give the datasets and code in supplemental material.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
also be provided via detailed
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open- spen-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
cases, in which
42

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: All of the datasets used in this paper public. The datasets and code of all algorithms are available at /ttttss///gtthiie thub. com/ TJU/OMS-DecD, D git
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https sowoodeeuumisssooooo..
//nips.co wwt.ccpppcccclcuccoocooooo hwllcc/ggiesssseee
for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We have clearly specified the experimental setting in appendix (Section including basic information datasets, the type of hyperparameters, the value of hyperparameters and
C
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to a level detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We have reported the error bar which is the standard deviation of the mean. We run each experiment 10 times, record the mean of 10 random results (including MSE and running time) and the standard deviation of the mean.
Guidelines:
The answer NA means that the paper does not include experiments.
43

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We have stated the compute resources in the experimental setting (Section C All algorithms are implemented with on Windows machine with 2.8 GHz (T)
i7-1 165G7 CPU.
Guidelines:
The answer means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported didn't it make it into the paper).
paper (e.g., preliminary or failed experiments that NeurlPS Code of Ethics https: httpr//p.....pbbloocccccccccadda
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the
Answer: [Yes]
Justification: We have reviewed the NeurlPS Code of Ethics and our research conforms with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
44

---

Justification:
We have included the broader impacts in appendix (Section
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deploymeett of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: Our paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We use public datasets and give the URL from which the datasets are down- loaded.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
45

---

The name of the license (e.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperssi thcode com comddatasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We have provided the code of our algorithms with simplified documentation available httttp:://gtthub..
Junf htt.://.oooouuutt-tt///o/-----e- git
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodll as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
46

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
47


Reviews:
[{"review_id": "jWsJPWqUYb", "reviewer": "Reviewer_N9xw", "summary": "This paper looks at the problem of Online Model Selection in a Decentralized context (OMS-DECD). The authors show the relationship of this problem class with multiple problem classes included Online Model Selection, federated learning, online multi-kernel learning etc. They consider two aspects of the problem 1. whether they can get a minimized regret for the OMS-DECD problem and 2. whether collaboration is necessary (between clients) to get privacy preserving version of regret. \nThe authors show initially a federated version of online mirror descent with no Local update which provides a bound on the regret. Additionally they develop a federated OMS algorithm which provides an upper bound on the regret and recreates the result of historical work. They also develop lower bound results for cooperative and non-cooperative algorithms. Finally they show that collaboration is unnecessary ( the best bounds are obtained without collaboration) when there are no computational constraints on the clients, thus generalizing the results of distributed online learning and collaboration is necessary if the computation cost is constrained to o(K) where K is the number of clients. Along the way they develop a new Berstein's inequality for a Martingale to show the high probability bounds on the regret making it a stronger bounds than in expectation.", "questions": "Addressed in the previous section. \nAdditionally I had a slightly naive question regarding how to compare the regret bound of the three algorithms in table 1. It seems like the FOMD-OMS is adding an additional term and can potentially have poorer regret if C and C_i are comparable. Are these regret bounds not to be compared as they might be due to different function classes?", "limitations": "No specific limitations.", "rating": 6, "confidence": 1, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "I have not checked the mathematical accuracy of the proofs but the results look novel and are well motivated in the context of recent work and connection with other recent results. This helps us provide a unique perspective about when collaboration is actually necessary (the authors claim that they are not required if we focus on only the statistical perspective and not the computational aspects of the algorithms) and also gives us high probability bounds on the regret.", "weaknesses": "The paper is difficult to follow at times due to the mathematical density. It would be better presented by motivating the actual theorems in the paper and pushing the mathematical proofs to the appendix possibly. In particular, it was a bit difficult to follow the connection between FOMD-no-LU and FOMD-OMS and why the authors promoted the first algorithm. Having these details summarized in a table/section would make the paper much more readable.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for offering valuable comments and suggestions. Next we answer the questions.\n\n**[Question 1]** The paper is difficult to follow at times due to the mathematical density.  It would be better presented by motivating the actual theorems in the paper. \n\n**[Answer]**  We will provide more insights into the theorems. We appreciate the reviewer’s valuable suggestions.\n\n**[Question 2]** It was a bit difficult to follow the connection between FOMD-No-LU and FOMD-OMS and why the authors promoted the first algorithm.\n\n**[Answer]** At a high level, **FOMD-No-LU is a federated algorithmic framework** that establishes the update rules in a general form, **from which we derive FOMD-OMS**. To be specific, FOMD-OMS updates hypotheses by federated online gradient descent (F-OGD), and updates sampling probabilities by federated exponential gradient descent (F-EGD). Both F-OGD and F-EGD can be derived from FOMD-No-LU, which is a federated mirror descent framework.\n\nTherefore, **in order to provide more concise presentations and theoretical analyses, we introduce FOMD-No-LU and establish a general regret bound for it**. We believe that both FOMD-No-LU and the general regret bound might be of independent interest.\n\n\n**[Question 3]** Are these regret bounds in Table 1 not to be compared as they might be due to different function classes? It seems like the FOMD-OMS is adding an additional term and can potentially have poorer regret if $\\mathfrak{C}$ and $\\mathfrak{C}_i$ are comparable.\n\n**[Answer]** Thanks for raising the question. Indeed, the regret bounds in Table 1 are comparable.\nRecalling that, for each $i=1,...,K$, we define $\\mathfrak{C}_i=\\Theta(U_i G_i+C_i)$ where $U_i$, $G_i$ and $C_i$ are problem-dependent constants, and $\\mathfrak{C}=\\max_i\\mathfrak{C}_i$. We have $\\mathcal{C}_i\\leq \\mathcal{C}$. Next we separately compare FOMD-OMS with POF-MKL [1] and eM-KOFL [2].\n\n**FOMD-OMS vs POF-MKL**. \n\nFrom Table 1, it can be verified that\n$$\n    \\mathfrak{C}_i M\\sqrt{T\\ln{K}}+\\sqrt{\\mathfrak{C}\\mathfrak{C}_iMKT} +\\frac{\\mathfrak{C}_iMT}{\\sqrt{D}}\n    <\n    \\mathfrak{C}M\\sqrt{KT}+\\frac{\\mathfrak{C}_iMT}{\\sqrt{D}}.\n$$\nThus **the regret bound of FOMD-OMS is better than that of POF-MKL**.\n\n**FOMD-OMS vs eM-KOFL**. \n\n(1) In the case of $K\\leq\\mathfrak{C}M/\\mathfrak{C}_i\\cdot\\ln{K}$, we have\n$$\n    \\mathfrak{C}_i M\\sqrt{T\\ln{K}}+\\sqrt{\\mathfrak{C}\\mathfrak{C}_iMKT}\n    +\\frac{\\mathfrak{C}_iMT}{\\sqrt{D}}\n    \\lesssim \\mathfrak{C}M\\sqrt{T\\ln{K}}+\\frac{\\mathfrak{C}_iMT}{\\sqrt{D}},\n$$\nwhere we use the notation $\\lesssim$ to hide constant factors. Thus **the regret bound of FOMD-OMS is better than that of eM-KOFL**. \n\n(2) In the csae of $K\\geq\\mathfrak{C}M/\\mathfrak{C}_i\\cdot\\ln{K}$, we have \n$$\n    \\mathfrak{C}M\\sqrt{T\\ln{K}}+\\frac{\\mathfrak{C}_iMT}{\\sqrt{D}}\n    \\lesssim\n    \\mathfrak{C}_i M\\sqrt{T\\ln{K}}+\\sqrt{\\mathfrak{C}\\mathfrak{C}_iMKT}\n    +\\frac{\\mathfrak{C}_iMT}{\\sqrt{D}}.\n$$\nThus **the regret bound of FOMD-OMS is worse than that of eM-KOFL**. If $K$ is sufficiently large, the regret bound of eM-KOFL is better than that of FOMD-OMS by a factor of $O(\\sqrt{K})$.\n\nFrom Table 1, we observe that FOMD-OMS significantly improves the computational complexity of POF-MKL and eM-KOFL (by a factor of $O(K)$), either maintaining a better regret bound or incurring only a small expense in the regret bound. \n\nFurthermore, the **collaboration is ineffective in POF-MKL and eM-KOFL**, while **it is effective in FOMD-OMS**.\n\n\n\n**Reference**\n\n[1] Pouya M. Ghari and Yanning Shen. Personalized online federated learning with multiple kernels. NeurIPS, 2022.\n\n[2] Songnam Hong and Jeongmin Chae. Communication-efficient randomized algorithm for multi-kernel online federated learning. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022.", "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": "", "extra_scores": {}}, {"review_id": "txYxW99z6X", "reviewer": "Reviewer_eZoF", "summary": "The paper proposes a new online multi-kernel federated learning algorithm. The proposed method works based on estimating the gradients by the clients to make collaborations among clients for online federated learning helpful. The paper analyzes the regret bound of the proposed algorithm.", "questions": "The paper states that some algorithms suffer from $\\mathcal O(K)$ download cost. However, based on my understanding download cost may not be that significant. Can you explain the importance of download cost?", "limitations": "Limitations adequately discussed.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The paper tries to address the important and interesting problem of benefit of collaboration in online model selection and online multi-kernel learning.\n2. The paper provides complete comparisons between regret upper of the proposed algorithm and those of other works.\n3. The paper is well-written and clear.", "weaknesses": "The proposed algorithm improves the regret of online multi-kernel learning by constant. Maybe adding some assumptions can help to achieve tighter regret bounds. Finding such conditions can be an interesting direction for future research.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for valuable comments and suggestions. Next we answer the questions.\n\n**[Question 1]** The proposed algorithm improves the regret of online multi-kernel learning by constant. Maybe adding some assumptions can help to achieve tighter regret bounds. Finding such conditions can be an interesting direction for future research.\n\n**[Answer]** We appreciate the reviewer’s valuable suggestion. It is interesting to explore conditions under which we can explicitly compare the constants.\n\n**[Question 2]** The paper states that some algorithms suffer from $O(K)$ download cost. Can the authors explain the importance of download cost? \n\n**[Answer]** This is a good question. There are algorithms that enjoy $O(\\log{K})$ upload cost, but suffer from $O(K)$ download cost, such as POF-MKL[1]. If $K$ is sufficiently large such that the speed of download is less than $K$ times of the speed of upload, then the download cost becomes the bottleneck in communication. Therefore, it is important to reduce the download cost for such algorithms.\n\n**Reference** \n\n[1] Pouya M. Ghari and Yanning Shen. Personalized online federated learning with multiple kernels. NeurIPS, 2022.", "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": "", "extra_scores": {}}, {"review_id": "4ceKPdO2vl", "reviewer": "Reviewer_EYSG", "summary": "This paper discusses the necessity of collaboration among clients in a decentralized data setting for online model selection. The authors analyze this necessity from the perspective of computational constraints and propose a new federated learning algorithm. They prove the upper and lower bounds of this algorithm. The main conclusion is that collaboration is unnecessary if there are no computational constraints on clients, but necessary if each client's computational cost is limited to o(K), where K is the number of candidate hypothesis spaces. The key contributions include establishing conditions under which collaboration is required, designing an improved federated learning algorithm (FOMD-OMS) separating model selection from client prediction, which improves regret bounds and enhances model selection performance at lower computational and communication costs.", "questions": "Please see the weaknesses part.\n\nQuestion 1: How does this work specifically differ from and improve upon federated online bandit algorithms? What are the unique challenges introduced with the online model selection setting?", "limitations": "The authors have adequately addressed the limitations and societal impact.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The paper provides a rigorous theoretical analysis of the necessity of collaboration in federated learning for online model selection, considering computational constraints.\n2. The algorithm demonstrates improved regret bounds and performance in model selection while maintaining low computational and communication costs.", "weaknesses": "1. The motivation for federated learning in the context of online model selection with decentralized data is not clearly articulated. It would be beneficial to provide more details to justify the need for federated learning for practical applications, such as the online hyperparameter tuning mentioned in the example.\n2. As shown in Section 4.4, the exact communication cost for $o(K)$ is $O(MJ\\log K)$, where $J$ may have the same order with $K$ and introduce a large communication cost. It would be better to discuss the choice of $J$ and provide the exact communication cost in the abstract and introduction part.\n3. The paper does not sufficiently discuss the difference from previous works on federated online bandits. Both settings involve selection among K options (arms or hypothesis spaces), and a detailed comparison would highlight the unique aspects of this work.\n3. When considering setting $K=1$, [1] achieve results $O(M\\sqrt{T}+\\sqrt{MT})$ result for federated adversarial linear bandits setting, which has a similar form compared to the result of this work. It would be better to discuss the technique challenge in the proof process.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for detailed comments and valuable suggestions. The suggestions will make our presentation more clear. Next we answer the questions.\n\n**[Question 1]** The motivation for federated learning in the context of OMS-DecD is not clearly articulated. It would be beneficial to provide more details to justify the need for federated learning for practical applications.\n\n**[Answer]** In many real-world scenarios, data are generated at the edge (e.g., smartphones, IoT devices). Transmitting vast amounts of data to a central server violates the privacy concerns. Federated Learning (FL) mitigates this by only sharing model updates, thereby perserving data privacy. \n\nIn computing scenarios with limited computational resources (e.g.,constrained memory and processing power), online algorithms deployed a single device could only perform approximate model selection and model updating, thereby leading suboptimal solutions. **FL aggregates information from various clients without inducing significant additional computational cost on each client, and thus have the potentials to improve the performance**. Our work further theoretically demonstrate that FL is necessary for OMS-DecD when the computational resources available on each client are limited.\n\n**[Question 2]** In the Introduction part, why the communication cost is $o(K)$ instead of the exact $O(MJ\\log(K))$. How to choose the value of $J$.\n\n**[Answer]** As stated in Section 4.5, if $J$ is of the same order as $K$, i.e., $J=\\Theta(K)$, then there is no need to use federated learning for OMS-DecD, and consequently, communication is unnecessary. In the case of $J=o(K)$, federated learning is necessary. In this case, the communication of our algorithm is also $o(K)$. Therefore, for convinence of presentation, we state that our algorithm has a $o(K)$ communication cost in the Introduction. \n\nAs stated in Section 5, setting $J=2$ is sufficient to achieve the desired improvement in the regret bound, time complexity, or communication complexity compared to previous algorithms. Actually, our algorithm explicitly balances the regret and computational cost by adjusting $J$. The larger the value of $J$, the smaller the regret bound becomes, while the larger the computational complexity increases.\n\n**[Question 3]** The paper does not sufficiently discuss the difference from previous works on federated online bandits. Both settings involve selection among $K$ options (arms or hypothesis spaces), and a detailed comparison would highlight the unique aspects of this work.\n\n**[Answer]** This paper focused on the work most related to OMS-DecD. We are happy to discuss federated bandits, such as federated $K$-armed bandits [1] and federated linear contextual bandits [2], in our revision. Next we detail the differences between federated bandits and OMS-DecD.\n\n(1)\tFor OMS-DecD, we do not require the examples $({\\bf x}^{(j)}_t,y^{(j)}_t)$, $t=1,…,T$, on each client to be i.i.d. (independent and identically distributed), in contrast, the rewards $r^{(j)}_t$, $t=1,...,T$, in both federated $K$-armed bandits or federated linear contextual bandits must be i.i.d. **The assumption of i.i.d. rewards makes collaboration effective for federated bandits (similar to federated stochastic optimization); however, this may not hold true for OMS-DedD**. Therefore, **it is a unique problem of OMS-DecD to study whether collaboration is effective.**\n\n(2)\tThe challenges posed by the two problems are distinctly different. The hypothesis space $\\mathcal{F}_i$, such as a RKHS, enjoys a complex structure, while an arm (or action) does not has a structure. We can measure the complexity of $\\mathcal{F}_i$ by $\\mathfrak{C}_i>0$, while there is not a complexity defined for an arm. **Thus algorithms for OMS-DecD must adapt to the complexity of individual hypothesis spaces, posing unique challenges on algorithm design and theoretical analysis.**\n\n**[Question 4]** When considering setting $K=1$, [3] achieves the $O(M\\sqrt{T}+\\mathrm{poly}(d)\\sqrt{MT})$ result for federated adversarial linear bandits, which has a similar form compared to the result of this work. It would be better to discuss the technical challenges in the proof.\n\n**[Answer]**\n(1)\tOur regret bounds necessitate an analysis for both federated online gradient descent (F-OGD) and federated exponential gradient descent (F-EGD). However, the proof in [3] focuses exclusively on F-OGD, but is not applicable to F-EGD. **The first technical challenge is to analyze the regret of F-EGD**. To this end, our proofs offer a template for analyzing federated online mirror descent, which can be applied to both F-OGD and F-EGD. It is interesting that we decouple the regret bound into two parts: the first part cannot be reduced by federated averaging, while the second part highlights the benefits of federated averaging (see Theorem 1).\n\n(2) Regarding the dependence on problem-specific constants, the regret bound in [3] differs significantly from our results. As elucidated in the answer for Question 3, algorithms for OMS-DecD must adapt to the complexity of individual hypothesis spaces. Thus **the second technical challenge is the derivation of a high-probability regret bound that adapts to the complexity of individual hypothesis spaces.** To address this issue, we establish a new Bernstein’s inequality for martingale.\n\nWe will incorporate the discussion in the revision. Thanks for the suggestion.\n\n**[Question 5]** How does this work specifically differ from and improve upon federated online bandit algorithms? What are the unique challenges introduced with the online model selection setting?\n\n**[Answer]** Please refer to the answer for Question 3.\n\n\n**Reference**\n\n[1] Wang et al. Distributed Bandit Learning: Near-Optimal Regret with Efficient Communication. ICLR, 2020.\n\n[2] Huang et al. Federated Linear Contextual Bandits. NeurIPS, 2021.\n\n[3] Patel, K. K., et al. Federated online and bandit convex optimization. ICML, 2023.", "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": "", "extra_scores": {}}, {"review_id": "tPX5KEUPAl", "reviewer": "Reviewer_83EK", "summary": "The paper studies the problem of regret minimization $ \\min_{f_1, \\ldots, f_T} \\left( \\sum_{t=1}^T \\ell(f_t(x_t), y_t) - \\min_{f \\in \\mathcal{F}^*} \\sum_{t=1}^T \\ell(f(x_t), y_t) \\right)$ in distributed settings with $M$ clients. The paper proves lower bounds on regret and introduces a federated algorithm with an upper bound analysis. The paper proves collaboration is unnecessary without computational constraints on sites and necessary if the computation per client is bounded by $o(K)$ where $K$ is the number of hypotheses ($F$).", "questions": "N/A", "limitations": "N/A", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "The paper made a strong contribution. It proposes a new algorithm that improves previous bounds on computation and communication costs and establishes interesting lower bounds on algorithms. The work presents three new techniques: improved Bernstein's inequality for martingales, a federated online mirror descent framework, and decoupling model selection and prediction. The technical contribution is sold, and the paper is well-written. The paper contains extensive experimental studies that support theoretical bounds.", "weaknesses": "I didn't see any significant weaknesses.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful to the reviewer for taking the time to evaluate our paper and for providing encouraging feedback. We will continue our research in this area to make more controbutions.", "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": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for taking the time to review our paper and offering valuable comments and suggestions.

In this paper, we address the fundamental problem of whether collaboration is necessary for online model selection with decentralized data (OMS-DecD). All reviewers acknowledged our theoretical contributions, which include the conditions under which collaboration is necessary for OMS-DecD and a clarification of the unnecessary nature of collaboration in previous federated algorithms for distributed online multi-kernel learning, and technical contributions, consisting of improved Bernstein's inequality for martingales, a federated online mirror descent framework, and decoupling model selection and prediction, all of which might be of independent interest.

The reviewers also rose some valuable questions. We have provided detailed answers to all of the questions. The reviewers also provided constructive suggestions that will make the presentation more clear and make our paper easier to follow. We will revise our paper following the suggestions.

Meta-review: This paper took a nice framework, federated learning, and provided some nice results around the problem of collaborating on model selection in a decentralized setting. The reviewers all agreed this was an interesting problem, had solid results, and deserved to be published. I would strongly recommend the authors take into account the critical feedback when preparing the paper for the camera-ready version.
Decision: Accept (poster)