On the Necessity of Collaboration for Online Model Selection with Decentralized Data

Authors: junfan  li
zheshun  wu
zenglin  xu
irwin  king
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 08:16:18

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.

Main paper: 
 introduction: 
 Model selection which is a fundamental problem for offline machine learning focuses on how to select a suitable hypothesis space for a machine learning algorithm [Mitchell, 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 [Karimi et al., 2021] , and model selection for contextual bandits [Foster et al., 2019 , Pacchiano et al., 2020 , Ghosh and Chowdhury, 2022] . We consider model selection for online supervised learning. Let F = {F 1 , . . . , F K } contain K hypothesis spaces and (•, •) be a loss function. For a sequence of examples {(x t , y t )} t=1,...,T , we aim to adapt to the case that the optimal hypothesis space F i * ∈ F is given by an oracle and we run an online learning algorithm in F i * . OMS can be defined by minimizing the regret, i.e., min f1,...,f T T t=1 (f t (x t ), y t ) -minf ∈F i * T t=1 (f (x t ), y t ) ,where f t ∈ ∪ K i=1 F i is the hypothesis used by an OMS algorithm at the t-th round. The optimal value of the regret depends on the complexity of F i * [Foster et al., 2017 [Foster et al., , 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 x (j) t , y (j) t t=1,...,T, j = 1, . . . , 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 et al., 2023a,b] . 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 et 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-DecD can be defined by minimizing the following regret, , y(j) t-minf ∈F i * M j=1 T t=1 f x (j) t , y (j) t   ,where f (j) t ∈ ∪ K i=1 F i is the hypothesis adopted by the j-th client at the t-th round. Solving OMS-DecD must achieve two goals: G1 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 a regret bound that increases linearly with M . It is unknown whether it achieves G1. Another approach is federated learning which is a framework of cooperative learning with privacy protection and is provably effective in stochastic convex optimization [McMahan et al., 2017 , Woodworth et al., 2020b , Wang et al., 2021 , Reddi et al., 2021] . It is natural to ask: Question 1. Whether collaboration is effective for OMS-DecD.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 i is a reproducing kernel Hilbert space (RKHS), and proposed three federated OMKL algorithms including vM-KOFL, eM-KOFL [Hong and Chae, 2022] 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-DecD is equivalent to distributed online learning [Mitra et al., 2021 , Kwon et al., 2023 , Patel et 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 answered 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.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 F 1 , ..., F K 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 1 summarizes the results.(2) Lower bounds on the regret. We separately prove a 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 1. By the upper bound and lower bounds, we conclude that (i) collaboration is unnecessary when there are no computational constraints on clients, thereby generalizing the result for distributed online learning, i.e., K = 1;(ii) collaboration is necessary if the computational cost on each client is limited to o(K) where irrelevant parameters are omitted. Our results clarify the unnecessary nature of collaboration in previous federated algorithms for distributed OMKL.There are two main technical challenges on designing a federated online model selection algorithm.The first challenge lies in obtaining high-probability regret bounds that adapt to the complexity of individual hypothesis space, a fundamental problem in online model selection [Foster et al., 2017] . While acquiring expected regret bounds that adapt to the complexity of individual hypothesis spaces is straightforward, the crux is to derive high-probability bounds from expected bounds. To this end, we introduce a new Bernstein's inequality for martingale (Lemma 1), which might be of independent interest.The second challenge involves achieving a per-round communication cost of o(K). To tackle this challenge, we propose two techniques: (i) decoupling model selection and prediction; (ii) an algorithmic framework, named FOMD-No-LU, which might be of independent interest. Specifically, when clients execute model selection, server must broadcast an aggregated probability distribution, denoted by p ∈ R K , 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 to clients. Additionally, if we 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. 
related work: 
 Previous work has studied the necessity of collaboration for distributed bandit convex optimization [Patel et al., 2023] , where a federated algorithmic framework named FEDPOSGD was proposed.Although the regret bounds of FEDPOSGD are smaller than some noncooperative algorithms, there is not a 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 is 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-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 (xEQUATIONt ), t = 1, . . . , T , on each client are 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 a distinctive problem for OMS-DecD to study whether collaboration is effective. 
problem setting: 
 Notations Let X = {x ∈ R d | x 2 < ∞} be an instance space, Y = {y ∈ R : |y| < ∞} be an output space, and {(x t , y t )} t∈[T ] be a sequence of examples, where [T ] = {1, . . . , T }, x t ∈ X and y t ∈ Y. Let S = {s 1 , s 2 , . . .} be a finite set, Uni(S) be the uniform distribution over the elements in S and s [T ] be the abbreviation of the sequence s 1 , s 2 , . . . , s T . Denote by P[A] the probability that an event A occurs, a ∧ b = min{a, b}, a ∨ b = max{a, b} and log(a) = log 2 (a). Let ψ t (•) : Ω → R, t ∈ [T ] be a sequence of time-variant strongly convex regularizers defined on a domain Ω. The Bregman divergence denoted byD ψt (•, •), associated with ψ t (•) is defined by ∀u, v ∈ Ω, D ψt (u, v) = ψ t (u) -ψ t (v) -∇ψ t (v), u -v .Let F = {F 1 , ..., F K } contain K hypothesis spaces whereEQUATIONLet F i * ∈ F be the optimal but unknown hypothesis space for a given {(x t , y t )} t∈ [T ] . OMS can be defined as follows: generating a sequence of hypotheses f [T ] that minimizes the following regret,∀i ∈ [K], Reg(F i ) = T t=1 (f t (x t ), y t ) -min f ∈Fi T t=1 (f (x t ), y t ),where f t ∈ ∪ K i=1 F i . The optimal hypothesis space F i * must contain a good hypothesis and has a low complexity [Foster et al., 2017 [Foster et al., , 2019]] , and is defined byF i * = arg min Fi∈F min f ∈Fi T t=1 (f (x t ), y t ) + Θ T • C i ,where C i measures the complexity of F i , such as U i and d i .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.Example 1 (Online Hyper-parameters Tuning). Let F i consist of linear functions of the formF i = {f (x) = w, x , w 2 ≤ U i } ,whereU i > 0 is a regularization parameter. Let U = {U i , i ∈ [K] : U 1 < U 2 < . . . < U K }.The hypothesis spaces are nested, i.e., F 1 ⊆ F 2 ⊆ . . . ⊆ F K . The optimal regularization parameter U i * ∈ U corresponds to the optimal hypothesis space F i * ∈ F.Example 2 (Online Kernel Selection [Shen et al., 2019, Li and Liao, 2022] ). Let κ i (•, •) : R d ×R d → R be a positive semidefinite kernel function, and φ i : R d → R di be the associated feature mapping. F i is the RKHS associated with κ i , i.e.,F i = {f (x) = w, φ i (x) : w 2 ≤ U i } .The optimal kernel function κ i * ∈ {κ 1 , . . . , κ K } corresponds to the optimal RKHS F i * ∈ F.Example 3 (Online Pre-trained Classifier Selection [Karimi et al., 2021] ). Generally, F i can be a well-trained machine learning model. Let F contain K pre-trained classifiers. For a new instance x t , 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.We formally define OMS-DecD as follows. Assuming that there are M clients and a server. At any round t, each client observes an instance x (j)t , and selects a hypothesis fEQUATION, where y(j)t is the label or true output. Each client can not share personalized data with others, but can share personalized models or gradients via the central server. 
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 Ω be a convex and bounded decision set. At any round t, each client j ∈ [M ] selects a decision u (j) t ∈ Ω, and then observes a loss function l(j) t (•) : Ω → R. The client computes the loss l (j) t (u (j) t )and an estimator of the gradient denoted by g(j)t (or the gradient denoted by g(j)t ). To reduce the communication cost, we adopt the intermittent communication (IC) protocol [Woodworth et al., 2021] where clients communicate with server every N rounds. Assuming that T = N × R where N, R ∈ Z, the IC protocol limits the rounds of communication to R.We divide [T ] into R disjoint sub-intervals denoted by {T r } R r=1 , in which T r = {(r -1)N + 1, (r -1)N + 2, . . . , rN } .(2)For any t ∈ T r , all clients always select the initial decision, i.e.,EQUATIONAt the end of the rN -round, all of clients send 1 N t∈Tr g(j) t , j ∈ [M ] to server. Then server updates the decision within online mirror descent framework [Bubeck and Cesa-Bianchi, 2012] ,EQUATIONEQUATION(4)-( 5) is called model averaging [McMahan et al., 2017] and shows the collaboration among clients. Finally, server may broadcast u t+1 to all clients. Let the initial decision u(j) 1 = u 1 for all j ∈ [M ], then it must be u (j) t = u t for all t ∈ [T ]. Thus clients do not transmit u (j) t to server. The pseudo-code of FOMD-No-LU is shown in Algorithm 1. 4.1 Regret Bound Theorem 1. Let E = {N, 2N, ...., RN } where N = T R and R ∈ [T ]. Assuming that l (j) t (•), t ∈ [T ], j ∈ [M ], are convex loss functions. Let g (j) t = ∇ u (j) t l (j) t (u (j) t ) and g(j)t be an estimator of g (j)t . At any round t ∈ E, let q t+1 and r t+1 be two auxiliary decisions defined as follows,∇ qt+1 ψ t (q t+1 ) = ∇ ut ψ t (u t ) -2 M j=1 g(j) t -g (j) t M , ∇ rt+1 ψ t (r t+1 ) = ∇ ut ψ t (u t ) - 2 M M j=1 g (j)t .Then FOMD-No-LU guarantees that,∀v ∈ Ω, T t=1 M j=1 l (j) t (u (j) t ) -l (j) t (v) N M ≤ t∈E D ψt (v, u t ) -D ψt (v, u t+1 ) + D ψt (u t , r t+1 ) 2 Ξ1 + t∈E D ψt (u t , q t+1 ) 2 + 1 M t∈E M j=1 g(j) t -g (j) t , u t -v Ξ2 .It is intriguing that the regret bound comprises two components: the first part, Ξ 1 , cannot be reduced by collaboration, while the second part, Ξ 2 , highlights the benefits of collaboration. Ξ 1 is the regret induced by exact gradients, while Ξ 2 is the regret induced by estimated gradients and shows how collaboration controls the regret. It is worth mentioning that Theorem 1 gives a general regret bound, from which various types of regret bounds can be readily derived by instantiating the decision set Ω and the regularizer ψ t (•). For instance, if Ω = F i whereEQUATION2 , then FOMD-No-LU becomes a federated online descent descent. It is easy to give a O(M U i (1 + C M )T ) expected regret from Theorem 1. Besides, N > 1 increases the regret and shows the trade-off between communication cost and regret bound.Theorem 1 requires a novel analysis on how the bias of estimators, i.e., M j=1 g(j)t -gEQUATION2 , is controlled by cooperation. To this end, we introduce two virtual decisions q t+1 and r t+1 that are updated by 2 M j=1 g(j)t -g(j) t M and 2 M j=1 g (j) tM , respectively. Previous federated online mirror descent uses exact gradients g [Mitra et al., 2021] . Thus its analysis is different from ours. (j) t , j ∈ [M ](R = T ) Require: T , J, η1, {Ui, λ1,i, i ∈ [K]} Ensure: f (j) 1,i = 0, p1,i, i ∈ [K], j ∈ [M ] 1: for t =In fact, FOMD-No-LU adopts the batching technique [Dekel et al., 2011] , that is, 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., 2012] and distributed stochastic convex optimization [Karimireddy et al., 2020 , Woodworth et al., 2020a] . We use the batching technique for the first time to distributed online learning.FOMD-No-LU is different from FedOMD (federated online mirror descent) [Mitra 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 Ξ 2 in Theorem 1. (ii) FedOMD uses local updating, such as local OGD [Patel et al., 2023] and local SGD [McMahan et al., 2017 , Reddi et al., 2021] . Thus FedOMD induces client drift, i.e., u (j) t = u t . Besides, if we use FedOMD to design a federated online model selection algorithm, then the download cost is in O(M K) 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 < T to the appendix. At a high level, our algorithm comprises two components both of which are critical for achieving a communication cost in o(K): (i) decoupling model selection and online prediction; (ii) collaboratively updating decisions within the framework of FOMD-No-LU.Model Selection on Server At any round t, server maintains K hypotheses {f(j) t,i ∈ F i } Ki=1 and a probability distribution p (j) t over the K hypotheses for all j ∈ [M ]. The model selection process aims to select a hypothesis from {f (j) t,i } K i=1 and then predicts the output of x (j)t . An intuitive idea is that, for each j ∈ [M ], the client samples a hypothesis following p (j) t . However, such an approach requires that server broadcasts p (j) t to clients, and will cause a download cost in O(K). The sampling operation (or model selection process) can be executed on server. Specifically, server just broadcasts the selected hypotheses, and thus saves the communication cost. For each j ∈ [M ], server selects J ∈ [2, K] hypotheses denoted by f (j) t for all j ∈ [M ] and thus must independently execute (7) M times which only pays an additional computational cost in O(M log K). The factor log K arises from the process of sampling a number from {1, ..., K}. Server only sends f(j)At,a , a ∈ [J] to the j-th client. It is worth mentioning that server does not send p t . The total download cost is O(M j=1 J a=1 (d At,a + log K)). If J is independent of K, then the download cost is only O(M log K).Prediction on Clients For each j ∈ [M ], the j-th client receives f(j)At,a , a ∈ [J], and uses f (j) t,At,1 to output a prediction, i.e., ŷ(j)t = f (j) t,At,1 x (j) t = w (j) t,At,1 , φ At,1 (x (j) t ) ,where we assume that f 1)). After observing the true output y (j) t , the client suffers a loss (f(j) t,i is parameterized by w (j) t,i ∈ R di (see ((j) t,At,1 (x (j) t ), y (j) t ).It is worth mentioning that the other J -1 hypotheses f (j) t,At,a , a ≥ 2 are just used to obtain more information on the loss function. We will explain more in the following subsection. Thus we do not cumulate the loss (f(j) t,At,a (x (j) t ), y (j) t ), a ≥ 2.Updating sampling probabilities For each j ∈ [M ], let c • I i∈O (j)(j) t = (c (j) t,1 , . . . , c (j) t,K ) where c (j) t,i = (f (j) t,i (x (j) t ), y (j) t ) is the loss of f (j) t,i , i ∈ [K]. The j-th client will send c (j) t,i , i ∈ O (j) t ,t , i ∈ [K].It is easy to prove that E t c(j)t,i = c (j) t,iand E t (c(j) t,i ) 2 ≤ K-1 J-1 (c (j) t,i ) 2 where E t [•] := E •|O (j) [t-1]. Thus sampling A t,a , a ≥ 2 reduces the variance of the estimators which is equivalent to obtain more information on the true loss.Server aggregates c(j) t , j ∈ [M ] and updates p t following (4)-(6). Let ∆ K be the (K-1)-dimensional simplex, Ω = ∆ K and g(j) t = c(j) t . Then the server executes (8).EQUATIONwhere ψ t (p) is the weighted negative entropy regularizer [Bubeck et al., 2017] , η t > 0 is a timevariant learning rate and C i > 0 satisfies that max t,j c (j) t,i ≤ C i . It is obvious that server does not broadcast p t+1 .For each j ∈ [M ] and i ∈ [K], let ∇ (j) t,i = ∇ w (j) t,i w (j) t,i , φ i (x (j) t ) , y (j) t . Since ∇ (j) t,i , i / ∈ O (j)t are unknown, it is necessary to construct an estimator of the gradient, denoted by ∇(j)t,i = ∇ (j) t,i P[i∈O (j) t ] • I i∈O (j) t for all j ∈ [M ], i ∈ [K]. Clients send {∇ (j) t,i , i ∈ O (j) t }, j ∈ [M ] to server. Then server aggregates { ∇(j) t,i , i ∈ [K]}, j ∈ [M ]and updates the hypotheses following (4)-( 6). For each i ∈ [K], let Ω = F i and g(j)EQUATIONwhere ψ t,i (w) is the Euclidean regularizer and λ t,i is a time-variant learning rate.We name this algorithm FOMD-OMS (FOMD-No-LU for OMS-DecD) and show it in Algorithm 2.To obtain high-probability regret bounds that adapt to the complexity of individual hypothesis space, we establish a new Bernstein's inequality for martingale. Lemma 1. Let X 1 , . . . , X n be a bounded martingale difference sequence w.r.t. the filtration H = (H k ) 1≤k≤n and with|X k | ≤ a. Let Z t = t k=1X k be the associated martingale. Denote the sum of the conditional variances byΣ 2 n = n k=1 E X 2 k |H k-1 ≤ v, where v ∈ [0, B] is a random variable and B ≥ 2 is a constant. Then for any constant a > 0, with probability at least 1 -2 log B δ, max t=1,...,n Z t < 2a 3 ln 1 δ + 2 B ln 1 δ + 2 v ln 1 δ .Note that v 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 1 is derived from the standard Bernstein's inequality along with the well-known peeling technique [Bartlett et al., 2005] . Shen, 2022, Hong and Chae, 2022] , that is, they can not adapt to the complexity of individual hypothesis space. If C i * C, then our regret bound is much better.Assumption 1. For each i ∈ [K], there is a constant b i such that φ i (x) 2 ≤ b i where φ i (•) is defined in (1). Lemma 2. Under Assumption 1, for each i ∈ [K], there are two constants C i > 0, G i > 0 that depend on U i or b i such that max t,j c (j) t,i ≤ C i and max t,j ∇ (j) t,i 2 ≤ G i . Theorem 2. Let R = T . Under Assumption 1, denote by A m = argmin i∈[K] C i and C = max i∈[K] C i . Assuming that (•, •) is convex and K ≥ J ≥ 2. Let g K,J = K-J J-1 , ∀i ∈ A m , p 1,i = 1 |A m | 1 - √ K √ T + 1 √ KT and ∀i / ∈ A m , p 1,i = 1 √ KT , ∀t ∈ [T ], η t = ln (KT ) 2 1 + g K,J M T ∧ 1 2g K,J , λ t,i = U i 2G i 1 + g K,J M • g 2 K,J ∨ t . With probability at least 1 -Θ (M log(T ) + log(KT /M )) • δ, the regret of FOMD-OMS satisfies: ∀i ∈ [K], Reg D (F i ) = O M B i,1 1 + g K,J M T + B i,2 • g K,J ln 1 δ + B i,3 g K,J M T ln 1 δ , where B i,1 = U i G i + C i ln(KT ), B i,2 = M C + U i G i and B i,3 = U i G i + √ CC i . Both C i and G i depend on U i or b i (see Lemma 2). Let C i = Θ(U i G i + C i ). Thus C i measures the complexity of F i . Then our regret bound adapts to √ CC i where C = max i∈[K] C i , while previous regret bounds depend on C [Ghari andThe regret bound in Theorem 2 is also called multi-scale regret bound [Bubeck et al., 2017] . However, previous regret analysis can not yield a high-probability multi-scale bound. The reason is the lack of the new Bernstein's inequality for martingale (Lemma 1). If we use the new Freedman's inequality for martingale [Lee et al., 2020] , then a high-probability bound can still be obtained, but is worse than the bound in Theorem 2 by a factor of order O(poly(ln T )).For each j ∈ [M ], the j-th client makes prediction and computes gradients in time O( i∈O (j)t d i ). Server samples O (j) t , j ∈ [M ],aggregates gradients and updates global models. The per-round time complexity on server is O(M j=1 i∈O (j) t d i + K i=1 d i + JM log K).Upload At any round t ∈ [T ], the j-th client transmits c(j) t,i , ∇ (j) t,i , i ∈ O (j)t and the corresponding indexes to server. It requires J( i∈O (j) t d i + 1) floating-point numbers and J integers. If we use 32 bits to represent a float, and use log K bits to represent an integer in [K] . Each client transmits (32J( i∈O (j)t d i + 1) + J log K) bits to server. Download Server broadcasts w t,i ∈ R di , i ∈ O (j) tand the corresponding indexes to clients. The total download cost is (32M J( i∈O (j)t d i + 1) + M J log K) bits.Before discussing Question 1, we give two lower bounds on the regret. Theorem 3 (Lower Bounds). Assuming that 5 ≤ K ≤ min{d, T }.For each i ∈ [K], let F i = {f i (x) = e i x} and D i = [min x∈X f i (x), max x∈X f i (x)], where e i is the standard basis vector in R d . Denote by sup the supremum over all examples. (i) There are no computational constraints on clients. Let (v, y) = |v -y|. The regret of any algorithm for OMS-DecD satisfies:lim T →∞ sup max i∈[K] Reg D (F i ) ≥ 0.25M √ T ln K; (ii) The per-round time complexity on each client is limited to O(J). Let (v, y) = 1 -v • y.The regret of any, possibly randomized, noncooperative algorithm with outputs in∪ i∈[K] D i for OMS-DecD satisfies: sup E[max i∈[K] Reg D (F i )] ≥ 0.1M √ KT J -1, where the expectation is taken over the randomization of algorithm.The assumption that the outputs of any noncooperative algorithm belong to ∪ i=∈[K] D i is natural, and can be removed in the case of J = 1. Next we define a noncooperative algorithm, NCO-OMS.O (j) t following (7) and executes ∀j ∈ [M ], ∇ pt+1 ψ t (p t+1 ) =∇ p (j) t ψ t p (j) t - c(j) t , p (j) t+1 = arg min p∈∆ K D ψt (p, pt+1 ). ∇ wt+1,i ψ t,i ( wt+1,i ) =∇ w (j) t,i ψ t,i w (j) t,i - ∇(j) t,i , w (j) t+1,i = arg min w∈Fi D ψt,i (w, wt+1,i ),where the definitions of c(j) t and ∇(j) t,i follow FOMD-OMS.It is easy to prove the regret of NCO-OMS satisfies: with probability at least1 -Θ (M log(KT )) • δ, ∀i ∈ [K], Reg D (F i ) = O M B i,1 (1 + g K,J ) T + B i,2 g K,J ln 1 δ + B i,3 g K,J T ln 1 δ , where B i,1 = U i G i + C i ln(KT ), B i,2 = C + U i G i and B i,3 = U i G i + √ CC i .We leave the pseudo-code of NCO-OMS and the corresponding regret analysis in appendix.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 a O(M U i G i √ T + M C i T ln(KT )) regret.By Theorem 3, 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 on each client is limited to o(K). Collaboration is necessary.Let J = o(K) in FOMD-OMS and Theorem 3. By Theorem 2, FOMD-OMS enjoys a O(M B i,1 √ T + B i,3 √ M KT J -1 ln δ -1) regret, which is 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 [Rahimi and Recht, 2007 ]. Time (s) is the per-round time complexity on client.Regret bound Time (s) Download (bits)eM-KOFL Õ CM √ T ln K + CiM T √ D O(DK) O(DM log K) POF-MKL Õ CM √ KT + CiM T √ D O(DK) O(DM K) FOMD-OMS Õ C i M √ T ln K + √ CC i M KT + CiM T √ D O(D) O(DM log K)6 Application to Distributed OMKLWe will apply the proposed FOMD-OMS to a special instance of OMS-DecD, known as distributed OMKL, in which F i 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 F i be a RHKS for all i ∈ [K] and R ≤ T . With probability at least 1 -Θ (T M log(R) + T log(KR/M )) • δ, the regret of FOMD-OMS satisfies, ∀i ∈ [K], Reg D (F i ) = Õ M B i,1 1 + g K,J M • T √ R + B i,2 M g K,J T R + B i,3 T √ R M g K,J + U i G i M T √ D ,where the notation Õ(•) hides polylogarithmic factor in δ -1 and D = d i follows (1).We defer the algorithm in appendix. Let R = T and J = 2. We compare FOMD-OMS with eM-KOFL [Hong and Chae, 2022] and POF-MKL [Ghari and Shen, 2022] . Table 1 gives the results.We observe that FOMD-OMS significantly improves the computational complexity of eM-KOFL and POF-MKL (by a factor of O(K)) on each client. The per-round time complexity of the two algorithms is O(DK). Recalling the answer to Question 1 (see Section 5.5), collaboration in eM-KOFL and POF-MKL is unnecessary.Next we compare the regret bound of the three algorithms. Recalling that C i ≤ C. The regret bounds of eM-KOFL and POF-MKL can not adapt to 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 i . (ii) In the case of K = O C Ci M • ln K , the regret bound of FOMD-OMS is better than that of eM-KOFL. (iii) In the case of K = Ω C Ci M • ln K , 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( √ K). 
conclusion: 
 In this paper, we have studied the necessity of collaboration for OMS-DecD from the perspective of computational constraints. We demonstrate that collaboration is unnecessary when there are no computational constrains on clients, while it becomes necessary if the time complexity on each client is limited to o(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. 
 
 Appendix: The main limitation of this work lies in the first lower bound in Theorem 3 that holds in the case of T → ∞. Although this lower bound nearly matches our upper bound asymptotically and is enough to answer Question 1, it is desired to establish a non-asymptotical lower bound, that is, the lower bound holds for any value of T .This work can be potentially applied to distributed online prediction tasks. We aim to address a 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-parameter of online learning algorithms. Thus our work can alleviate the burden of machine learning engineers and improve the utility of online leaning algorithms in industrial applications.In this section, we aim to verify the following three goals which are our main results.G1 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 on 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 1). G2 Collaboration is necessary if we limit the computational cost on 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 O(1). We aim to verify that FOMD-OMS enjoys better prediction performance than NCO-OMS with J = 2. G3 FOMD-OMS improves the regret bounds of algorithms for distributed OMKL.FOMD-OMS with R = T and J = 2 enjoys similar prediction performance with eM-KOFL [Hong and Chae, 2022] , and enjoys better prediction performance than POF-MKL [Ghari and Shen, 2022] at a smaller computational cost on each client.Although there are more 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.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 to simulate the distributed implementation.To verify G1 and G2, we use the instance of online model selection given in Example 1. The first experiment verifies G1. We construct 10 nested hypothesis spaces (i.e., K = 10) as follows∀i ∈ [10], F i = {f (x) = w, x , w 2 ≤ U i } ,whereU i = i 10 . We set R = T and J = K in FOMD-OMS. Since J = K, we have O (j) t = [K] and P i ∈ O (j) t = 1. The learning rates η t , λ t,i , i ∈ [K] of FOMD-OMS follow Theorem 2.For NCO-OMS, we set J = K and set the learning rate η t , λ t,i , i∈ [K] following Theorem 2 in which M = 1, i.e., ∀t ∈ [T ], η t = ln (KT ) 2 √ T , λ t,i = U i 2G i √ t .We use the square loss function (f (x), y) = (f (x) -y) 2 . For both FOMD-OMS and NCO-OMS, we tune G i = (U i + 1) × {1, 2, 4, 6, 8, 10} and set The second experiment verifies G2. We set R = T and J = 2 in FOMD-OMS. The learning rates of FOMD-OMS also follow Theorem 2. For NCO-OMS, we also set J = 2 and set the learning rateC i = (U i + 1) 2 .η t , λ t,i , i ∈ [K] following Theorem 2 in which M = 1, i.e., ∀t ∈ [T ], η t = ln (KT ) 2 (K -1) T ∧ 1 2(K -2) , λ t,i = U i 2G i (K -1) • ((K -2) 2 ∨ t) .Similar to the first experiment, we tune G i = (U i + 1) × {1, 2, 4, 6, 8, 10} and setC i = (U i + 1) 2 .The third experiment verifies G3. We consider online kernel selection (as known as online multikernel learning) which is an instance of online model selection given in Example 2. We select the Gaussian kernel with 8 different kernel widths (i.e., K = 8),∀i ∈ [8], κ i (x, v) = exp - x -v 2 2 2σ 2 i , σ i = 2 i-2 ,and construct the corresponding hypothesis space F i and H i following (21) in which we setU i = U and D i = D for all i ∈ [K] and tune U ∈ {1, 2, 4}. Note that U i is same for all i ∈ [K].We replace the initial distribution p 1 in Theorem 2 with a uniform distribution ( 1 K , . . . , 1 K ). We set D = 100 for FOMD-OMS, eM-KOFL and POF-MKL. D is the number of random features. We set R = T , J = 2 and C = U + 1 in FOMD-OMS. Thus the per-round time complexity on each client is O(D) and the per-round communication cost is O(M D + M log K). There are three hyper-parameters in eM-KOFL, i.e., η g , η l and λ. η g is the global learning rate, η l is the local learning rate and λ is a regularization parameter. There are 2M + 3 hyper-parameters in POF-MKL, i.e., η g , η j , ξ j , j ∈ [M ], m, λ in which M/m plays the same role with J in FOMD-OMS. η g is the global learning rate, η j is the local learning rate, ξ j is called exploration rate and λ is a regularization parameter. Since J = 2 in FOMD-OMS, we can set m = M/2 for FOMD-OMS. Following the original paper [Ghari and Shen, 2022] , we set ξ j = 1. For a fair comparison, we change the learning rates of FOMD-OMS, eM-KOFL and POF-MKL. Following the parameter setting of eM-KOFL [Hong and Chae, 2022] , we tune η g , η l , η j ∈ {0.1, 0.5, 1, 4, 8, 16} and λ ∈ {0.1, 0.001, 0.0001} for eM-KOFL and POF-MKL. For FOMD-OMS, we also tune η t , λ t,i ∈ {0.1, 0.5, 1, 4, 8, 16}.For all of the three experiments, we set 10 clients, i.e., M = 10. We use 8 regression datasets shown in Table 2 from WEKA 2 [Hall et al., 2009] and UCI machine learning repository3 , 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 10 subsets and each subset simulates the data on a 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) i7-1165G7 CPU4 .We use the square loss function and define the mean squared error (MSE) of all algorithms, i.e.,MSE = 1 M T M j=1 T t=1 f (j) t x (j) t -y (j) t 2 .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. We summary the experimental results of the first and the second experiments in Table 3 .In Table 3 , ∆ is defined as the difference of MSE between NCO-OM and FOMD-OMS. Thus ∆ 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 are 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 ∆ is very small. Thus collaboration does not significantly improve the prediction performance of the noncooperative algorithm. The results verify the first goal G1.Next we consider the case J = 2 in which the per-round time complexity on each client is O(1). It is obvious that FOMD-OMS performs better than NCO-OMS on all datasets. Besides, the value of ∆ in the case of J = 2 is much larger than that in 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.Finally we 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 p t using an additional binary search on each client (see Section G.1). In other words, NCO-OMS must execute binary search M times at each round. FOMD-OMS only executes one binary search on server at each round. The improvement on the computational cost is benefit from decoupling model selection and prediction.We summary the experimental results of the third experiment in Table 4 . We first compare FOMD-OMS with eM-KOFL. As a whole, the MSE of the two algorithms is similar. On 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 a similar regret bound with eM-KOFL at a much smaller computational cost on the clients.Next we 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 at a much smaller computational cost on the clients.Thus the results in Table 4 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 not use federated learning to learn a global probability distribution denoted by p t , but learns a personalized probability distribution denoted by p t,j on each client. Thus POF-MKL converges to the best kernel function at a lower rate.(2) POF-MKL uniformly samples two kernel functions and then learns two global hypotheses, while FOMD-OMS uses p t to sample a kernel function and learns a 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 hypotheses using p t,j . Thus the time complexity is in O(DK). FOMD-OMS executes model selection on server, and only uses the sampled hypothesis to make prediction. Thus the time complexity on each client is in O(D).Let R < T . Clients communicate with server every N rounds. At the r-th communication, clients transmit{ 1 N t∈Tr ∇ (j) t,i , 1 N t∈Tr c (j) t,i } i∈O (j)t to server at the last round in T r . Then server updates sampling probabilities and hypotheses. We give the pseudo-code in Algorithm 3.Algorithm 3 FOMD-OMS (R < T ) Require: U , T , R, J. Ensure: f (j) 1,i = 0, p1,i, i ∈ [K], j ∈ [M ] 1: for r = 1, 2, . . . , R do 2:for t ∈ Tr do 3:if t == (r -1)N + 1 then 4:for j = 1, . . . , M do 5:Server samples O (j) t following (7) 6:Server transmits f(j) t,i , i ∈ O (j) tto the j-th client 7:end for 8:end if 9:for j = 1, . . . , M in parallel do 10:Output f (j) Theorem 5. Let R < T . For any t ∈ [R], let ∀i ∈ A m , p 1,i = 1 |A m | 1 - √ K √ R + 1 √ KR and ∀i / ∈ A m , p 1,i = 1 √ KR , ∀t ∈ [R], η t = ln (KR) 2 1 + g K,J M R ∧ 1 2g K,J , λ t,i = U i 2G i 1 + g K,J M • g 2 K,J ∨ t .Under the condition of Theorem 2, with probability at least1-Θ T R M log(R) + T R log(KR/M ) •δ, the regret of FOMD-OMS satisfies: ∀i ∈ [K], Reg D (F i ) = O M B i,1 1 + g K,J M • T √ R + T R • B i,2 M g K,J ln 1 δ + B i,3 T √ R M g K,J ln 1 δ .The regret bound depends on O( 1 √ R ). Thus FOMD-OMS explicitly balances the prediction performance and the communication cost.Proof. If FOMD-OMS runs on a sequence of examples with length T = R, then Theorem 2 gives, with probability at least 1 -Θ (M log(CR) + log(CKR/M )) • δ,Reg D (F i ) = O M B i,1 1 + g K,J M R + B i,2 g K,J ln 1 δ + B i,3 g K,J M R ln 1 δ .According to Theorem 1, the regret bound of FOMD-OMS with R < T satisfies, with probability at least 1 -Θ T R M log(CR) + T R log(CKR/M ) • δ, Reg D (F i ) =O N M B i,1 1 + g K,J M R + N B i,2 g K,J ln 1 δ + N B i,3 g K,J M R ln 1 δ =O T √ R M B i,1 1 + g K,J M + T R • B i,2 g K,J ln 1 δ + T √ R B i,3 g K,J M ln 1 δ ,which concludes the proof.We first state a technical lemma. Lemma 3 (Boyd and Vandenberghe [2004] ). Assuming that ψ(•) : X → R is a convex and differential function, and X is a convex domain. Let f * = argmin f ∈X ψ(f ). Then it must be ∀g ∈ X , ∇ψ(f * ), g -f * ≥ 0.Lemma 3 gives the first-order optimality condition.Proof of Theorem 1. We first consider the case R = T .The main idea is to give an lower bound and upper bound on ḡt , u t+1 -v , respectively. Next we give an upper bound.ḡt , u t+1 -v = ∇ ut ψ t (u t ) -∇ ūt+1 ψ t (ū t+1 ), u t+1 -v = ∇ ut ψ t (u t ) -∇ ut+1 ψ t (u t+1 ), u t+1 -v + ∇ ut+1 ψ t (u t+1 ) -∇ ūt+1 ψ t (ū t+1 ), u t+1 -v =D ψt (v, u t ) -D ψt (v, u t+1 ) -D ψt (u t+1 , u t ) -∇ ut+1 D ψt (u t+1 , ūt+1 ), v -u t+1 ≤D ψt (v, u t ) -D ψt (v, u t+1 ) -D ψt (u t+1 , u t ).The last inequality comes from Lemma 3.Then we give a lower bound.ḡt , u t+1 -v = 1 M M j=1 g (j) t , u t+1 -v + g(j) t -g (j) t , u t+1 -v = 1 M M j=1 g (j) t , u (j) t -v + 1 M M j=1 g (j) t , u t+1 -u t Ξ1 + 1 M M j=1 g(j) t -g (j) t , u t+1 -v Ξ2 ,where u(j) t = u t . Next we analyze Ξ 1 and Ξ 2 .To analyze Ξ 1 , we introduce an auxiliary variable r t+1 defined as follows∇ rt+1 ψ t (r t+1 ) = ∇ ut ψ t (u t ) - 2 M M j=1 g (j)t .Then we haveΞ 1 = 1 2 2 M M j=1 g (j) t , u t+1 -u t = 1 2 ∇ ut ψ t (u t ) -∇ rt+1 ψ t (r t+1 ), u t+1 -u t = 1 2 (D ψ (u t+1 , r t+1 ) -D ψ (u t+1 , u t ) -D ψ (u t , r t+1 )) ≥ - 1 2 (D ψ (u t+1 , u t ) + D ψ (u t , r t+1 )) .Before analyzing Ξ 2 , we also introduce an auxiliary variable q t+1 defined as follows∇ qt+1 ψ t (q t+1 ) = ∇ ut ψ t (u t ) - 2 M M j=1 g(j) t -g (j) t .Now we can analyze Ξ 2 . We haveΞ 2 = 1 2 2 M M j=1 g(j) t -g (j) t , u t+1 -u t + 1 M M j=1 g(j) t -g (j) t , u t -v Ξ3 = 1 2 ∇ ut ψ t (u t ) -∇ qt+1 ψ t (u t+1 ), u t+1 -u t + Ξ 3 = 1 2 (D ψ (u t+1 , q t+1 ) -D ψ (u t+1 , u t ) -D ψ (u t , q t+1 )) + Ξ 3 ≥ - 1 2 (D ψ (u t+1 , u t ) + D ψ (u t , q t+1 )) + Ξ 3 .Combining the lower bound and upper bound gives1 M M j=1 g (j) t , u (j) t -v ≤D ψt (v, u t ) -D ψt (v, u t+1 ) + Ξ 3 + 1 2 D ψ (u t , q t+1 ) + 1 2 D ψ (u t , r t+1 ).Using the convexity of lEQUATIONt -v , we further obtain1 M M j=1 l (j) t (u (j) t ) -l (j) t (v) ≤D ψt (v, u t ) -D ψt (v, u t+1 ) + 1 2 D ψ (u t , q t+1 ) + 1 2 D ψ (u t , r t+1 ) + Ξ 3 ,which concludes the proof. Now we consider the case R < T .Recalling that E = {N, 2N, 3N . . . , RN } and T r = {(r -1)N + 1, (r -1)N + 2, . . . , rN }, r = 1, . . . , R.For any batch T r , r = 1, . . . , R, we define a new loss function l(j) rN (•) at the end of this batch, ∀j ∈[M ], ∀u ∈ Ω, l(j) rN (u) = 1 N τ ∈Tr l (j) τ (u).During each batch, our algorithmic framework does not change the decision, i.e.,EQUATIONt = u (j) (r-1)N +1 . Thus the regret can be decomposed as follows, t (u1 M T t=1 M j=1 l (j) t (u (j) t ) -l (j) t (v) = 1 M R r=1   t∈Tr M j=1 l (j) t (u (j) (r-1)N +1 ) -l (j) t (v)   = N M R r=1   M j=1 t∈Tr 1 N l (j) t (u (j) (r-1)N +1 ) -l (j) t (v)   = N M R r=1 M j=1 l(j) rN (u (j) (r-1)N +1 ) - l(j) rN (v) .(j) t ) -l (j) t (v) ≤ t∈E D ψt (v, u t ) -D ψt (v, u t+1 ) + 1 2 D ψt (u t , q t+1 ) + 1 2 t∈E D ψt (u t , r t+1 ) + 1 M t∈E M j=1 g(j) t -g (j)t , u t -v , which concludes the proof.Lemma 4 (Bernstein's inequality for martingale). Let X 1 , . . . , X n be a bounded martingale difference sequence w.r.t. the filtration H = (H k ) 1≤k≤n and with |X k | ≤ a. Let Z t = t k=1 X k be the associated martingale. Denote the sum of the conditional variances byΣ 2 n = n k=1 E X 2 k |H k-1 ≤ v.Then for all constants a, v > 0, with probability at least 1 -δ, max t=1,...,nZ t < 2 3 a ln 1 δ + 2v ln 1 δ .Note that v must be a constant. Lemma 4 is derived from Lemma A.8 in [Cesa-Bianchi and Lugosi, 2006] .Proof. Let v ∈ [0, B] is a random variable and B ≥ 2 is a constant. We use the well-known peeling technique [Bartlett et al., 2005] . We divide the interval [0, B] as follows[0, B] ⊆ 0, 2 -log B log B j=-log B +1 2 j-1 , 2 j . First, we consider the case v > 2 -log B . Let = 2 3 a ln 1 δ + 2 v ln 1 δ > 2 3 a ln 1 δ + 2 2 -1-log B ln 1 δ = 2 3 a ln 1 δ + 2 B ln 1 δ .We decompose the random event as follows,P max t=1,...,n Z t > , Σ 2 n ≤ v, v > 2 -log B =P max t≤n Z t > , Σ 2 n ≤ v, ∪ log B i=-log B +1 2 i-1 < v ≤ 2 i ≤P max t≤n Z t > i , Σ 2 n ≤ v, ∪ log B i=-log B +1 2 i-1 < v ≤ 2 i ≤ log B i=-log B +1 P max t≤n Z t > i , Σ 2 n ≤ v, 2 i-1 < v ≤ 2 i ,where i = 2 3 a ln 1 δ + 2 2 i-1 ln 1 δ . For each sub-event, Lemma 4 yieldsP max t≤n Z t > i , Σ 2 n ≤ v, 2 i-1 < v ≤ 2 i ≤ δ.Thus we haveP max t∈[n] Z t > , Σ 2 n ≤ v, v > 2 -log B ≤ log B i=-log B +1 δ ≤ 2 log B δ.Then we consider the case v ≤ 2 -log B ≤ 1 B . Lemma 4 yields, with probability at least 1 -δ, max t=1,...,nZ t ≤ 2 3 a ln 1 δ + 2 1-log B ln 1 δ ≤ 2 3 a ln 1 δ + 2 B ln 1 δ .Combining the two cases, with probability at least 1 -2 log B δ, max t=1,...,nZ t ≤ 2a 3 ln 1 δ + 2 B ln 1 δ + 2 v ln 1 δ ,which concludes the proof.G.1 OMD with the weighted negative entropy regularizerLet Ω = ∆ K and ψ t (p) =Ci ηt p i ln p i . Then we have∀p ∈ R K , ∇ pi ψ t (p) = C i η t (ln p i + 1) , ∇ 2 i,i ψ t (p) = C i η t p i .The Bregman divergence associated with the negative entropy regularizer isEQUATION) Denote by ct = 1 M M j=1 c(j) t .Recalling that the OMD is defined as follows,∇ pt+1 ψ t (p t+1 ) = ∇ pt ψ t (p t ) -ct , p t+1 = arg min p∈∆ K D ψt (p, pt+1 ).Substituting into the gradient of ψ t , the mirror updating can be simplified.∀i ∈ [K], pt+1,i = p t,i • exp - η t ct,i C i .Now we use the Lagrangian multiplier method to solve the projection associated with Bregman divergence.L(p, λ) = 1 η t K i=1 C i p i ln p i pt+1,i + pt+1,i -p i + λ K i=1 p i -1 - K i=1 β i p i .The KKT conditions are∂L ∂p i = C i ln p i + 1 -ln pt+1,i -1 η t + λ -β i = 0, ∂L ∂λ = K i=1 p i -1 = 0, β i p i = 0.Let p t+1 , λ * and {β * i } K i=1 be the optimal solution. By the KKT conditions, we havep t+1,i =p t+1,i • exp - η t (λ * -β * i ) C i , K i=1 pt+1,i • exp - η t (λ * -β * i ) C i = K i=1 p t,i • exp - η t (λ * -β * i + ct,i ) C i = 1, β * i =0, in which the last equality comes from p t+1,i > 0. The reason is that by the fact p 1,i > 0 for all i ∈ [K], we can iteratively prove that p t,i > 0 and p t+1,i > 0, satisfying the condition under which β * i = 0. Then we can obtain the solution p t+1 , i.e.,EQUATION)Next we prove that λ * can be found by the binary search.If λ * ≥ 0, thenK i=1 p t,i • exp - ηt(λ * +ct,i) Ci ≤ K i=1 p t,i ≤ 1. If λ * ≤ -max i ct,i , then K i=1 p t,i • exp - ηt(λ * +ct,i) Ci ≥ K i=1 p t,i ≥ 1. Thus it must be -max i ct,i ≤ λ * ≤ 0. For any 0 ≥ λ 1 ≥ λ 2 ≥ -max i ct,i , we can obtain K i=1 p t,i • exp - η t (λ 1 + ct,i ) C i ≤ K i=1 p t,i • exp - η t (λ 2 + ct,i ) C i . Thus K i=1 p t,i • exp - ηt(λ * +ct,i) Ciis non-increasing w.r.t. λ * . We can use the binary search to find λ * .Let Ω = F i and ψ t,i (w) = 1 2λt,i w 2 2 . Then we have∀w ∈ R di , ∇ w ψ t,i (w) = 1 λ t,i w, ∇ 2 w ψ t,i (w) = 1 λ t,i , D ψt,i (w, v) = 1 2λ t,i w -v 2 2 .Recalling that the OMD is defined as follows, ∇ wt+1,i ψ t,i ( wt+1,i ) = ∇ wt,i ψ t (w t,i ) -∇t,i , w t+1,i = arg min w∈Fi D ψt,i (w, wt+1,i ).The mirror updating is as follows,∀i ∈ [K], wt+1,i =w t,i -λ t,i • ∇t,i , w t+1,i = min 1, U i wt+1,i 2 • wt+1,i .Thus OMD with the Euclidean regularizer is online gradient descent [Zinkevich, 2003] .Recalling that c(j) t,i = (f (j) t,i (x (j) t ), y (j) t ), in which f (j) t,i (x (j) t ) = w (j) t,i , φ i (x (j) t ) ≤ U i b i . Since |y (j) t | is uniformly bounded for all j ∈ [M ] and t ∈ [T ], there is a constant C i that depends on U i and b i such that c (j) t,i ≤ C i . Recalling that ∇ (j) t,i = (f (j) t,i (x (j) t ), y (j) t ) • φ i (x (j) t ). Since (f (j) t,i (x (j) t ), y (j)t ) can be upper bounded by C i and φ i (x(j) t ) 2 ≤ b i , there is a constant G i that depends on U i and b i such that ∇ (j) t,i 2 ≤ G i .The regret w.r.t. any f ∈ F i can be decomposed as follows.T t=1 M j=1 f (j) t,At,1 (x (j) t ), y (j) t - T t=1 M j=1 f (x (j) t ), y (j) t = T t=1 M j=1 f (j) t,At,1 (x (j) t ), y (j) t -f (j) t,i (x (j) t ), y (j) t + f (j) t,i (x (j) t ), y (j) t -f (x (j) t ), y (j) t = T t=1 M j=1 c (j) t,At,1 -c (j) t,i Ξ4 + T t=1 M j=1 f (j) t,i (x (j) t ), y (j) t -f (x (j) t ), y (j) t Ξ5 .Next we separately give an upper bound on Ξ 4 and Ξ 5 .We start with Lemma 1 and instantiate some notations.EQUATION)Recalling thatEQUATIONEQUATIONIn ( 13), we redefine Ω = ∆ K and ψ t (p) =Ci ηt p i ln p i , and in ( 14), we redefine Ω = ∆ K andEQUATIONIt can be verified that δt,i ∈ [-2C i , 2 K-J J-1 C i ] and ĉt,i ∈ [0, 2C i ].Recalling the definition of learning rate η t in Theorem 2. We can obtain ηtδt,iCi ≥ -1 and ηt ĉt,i 2Ci ≥ -1. Next we use ( 10) and ( 15) to analyze the following two Bregman divergences.T t=1 D ψt (p t , r t+1 ) = T t=1 1 η t K i=1 2C i • p t,i ln p t,i r t+1,i + r t+1,i -p t,i = T t=1 1 η t K i=1 2C i • p t,i η t ĉt,i 2C i + p t,i • exp - η t ĉt,i 2C i -p t,i ≤ T t=1 1 η t K i=1 2C i • p t,i η t ĉt,i 2C i + p t,i • 1 - η t ĉt,i 2C i + η t ĉt,i 2C i 2 -p t,i ≤ T t=1 η t K i=1 p t,i 2C i   2 M M j=1 c (j) t,i   2 ≤2 T t=1 η t • 1 M M j=1 K i=1 p t,i c (j) t,i ,andT t=1 D ψt (p t , q t+1 ) = T t=1 1 η t K i=1 C i p t,i ln p t,i q t+1,i + q t+1,i -p t,i = T t=1 1 η t K i=1 C i p t,i η t δ t,i C i + p t,i • exp - η t δ t,i C i -p t,i ≤4 T t=1 η t K i=1 p t,i C i   1 M M j=1 c(j) t,i -c (j) t,i   2 ,in where we use the fact exp(-x) ≤ 1 -x + x 2 for all x ≥ -1.Substituting the two upper bounds into (12) gives∀v ∈ ∆ K , 1 M T t=1 M j=1 c (j) t , p (j) t -v Ξ4,1 ≤ T t=1 (D ψt (v, p t ) -D ψt (v, p t+1 )) Ξ4,2 +2 T t=1 η K i=1 p t,i C i   1 M M j=1 c(j) t,i -c (j) t,i   2 Ξ4,3 + T t=1 η M M j=1 K i=1 p t,i c (j) t,i + 1 M T t=1 M j=1 c(j) t -c (j) t , p t -v Ξ4,4.Bounding Ξ 4,1We define a random variable X t as follows,EQUATION.Let H t = {O (1) t , . . . , O (M ) t }. Then we have E[X t |H [t-1] ] = 0 and |X t | ≤ C where C = max i C i . Thus X [T ] is a bounded martingale difference sequence w.r.t. the filtration H [T ] . The sum of condition variance satisfies T t=1 E |X t | 2 |H [t-1] ≤ T t=1 E c (j) t,At,1 2 |H [t-1] ≤ C • T t=1 c (j) t , p (j) t ≤ C 2 T.The upper bound is a random variable. Lemma 1 yields, with probability at least1 -M log(C 2 T )δ, Ξ 4,1 ≥ T t=1 M j=1 c (j) t,At,1 - T t=1 M j=1 c (j) t , v - 2CM 3 ln 1 δ -2 CM • M j=1 T t=1 c (j) t , p (j) t • ln 1 δ ,where the fail probability comes from the union-of-events, and the lower order term M 2C 2 T ln 1 δ is omitted. Bounding Ξ 4,2According to (10), we haveΞ 4,2 ≤ D ψ1 (v, p 1 ) = 1 η K i=1 C i v i ln v i p 1,i + p 1,i -v i ≤ C i η ln 1 p 1,i + 1 η K k=1 C k p 1,k - C i η .Bounding Ξ 4,3We define a random variable X t as follows,X t = K i=1 p t,i C i   1 M M j=1 c(j) t,i -c (j) t,i   2 -E t    K i=1 p t,i C i   1 M M j=1 c(j) t,i -c (j) t,i   2    . It can be verified that E[X t |H [t-1] ] = 0 and |X t | ≤ K-J J-1 C. Next we upper bound the sum of condition variance. T t=1 E t [X 2 t ] ≤ T t=1 E t       K i=1 p t,i C i   1 M M j=1 c(j) t,i -c (j) t,i   2    2    ≤ T t=1 E t    K i=1 p t,i    1 C i   1 M M j=1 c(j) t,i -c (j) t,i   2    2    ≤ (K -J) 2 (J -1) 2 T t=1 E t    K i=1 p t,i   1 M M j=1 c(j) t,i -c (j) t,i   2    = (K -J) 2 (J -1) 2 1 M 2 T t=1 K i=1 p t,i E t   M j=1 c(j) t,i -c (j) t,i 2   ≤ (K -J) 3 (J -1) 3 M 2 C • T t=1 M j=1 c (j) t , p (j) t ≤ (K -J) 3 (J -1) 3 M C 2 T,where we use the fact c(j)t,i = c (j) t,i P i∈O (j) t ≥ K-1 J-1 c (j)t,i . Lemma 1 yields, with probability at least1 -log(C 2 K 3 T /M )δ, Ξ 4,3 ≤ η   g K,J M 2 T t=1 M j=1 c (j) t , p (j) t + 2Cg K,J 3 ln 1 δ + 2 g 3 K,J M 2 C T t=1 M j=1 c (j) t , p (j) t • ln 1 δ   ,where g K,J = K-J J-1 and the lower order term2M g 3 K,J C 2 T ln 1 δ is omitted. Bounding Ξ 4,4We define a random variable X t as follows,EQUATION+ 2 g K,J M 2 • T t=1 M j=1 c (j) t ⊗ c (j) t , v ≤ 4C 2 KT M ,where c(j) t ⊗ c (j) t , v = K i=1 v i (c (j) t,i ) 2 . With probability at least 1 -log(4C 2 KT /M )δ, Ξ 4,4 ≤ 2Cg K,J 3 ln 1 δ + 2 2 g K,J M 2 ln 1 δ • C T t=1 M j=1 c (j) t , p (j) t + T t=1 M j=1 c (j) t ⊗ c (j) t , v .For simplicity, we introduce some new notationsLT = T t=1 M j=1 c (j) t , p (j) t , LT (v) = T t=1 M j=1 c (j) t , v , LT (v) = T t=1 M j=1 c (j) t ⊗ c (j) t , v .Combining all gives, with probability at least1 -Θ(log(CKT /M )) • δ, LT -LT (v) ≤ M η C i ln 1 p 1,i + K k=1 C k p 1,k -C i + η 1 + g K,J M LT + 2M C 3 g K,J ln 1 δ + 2 g 3 K,J C • LT • ln 1 δ + 2M Cg K,J 3 ln 1 δ + 2 2g K,J ln 1 δ • C LT + LT (v).Rearranging terms gives1 -η 1 + g K,J M LT -2η g 3 K,J C ln 1 δ + 2 2g K,J C ln 1 δ LT ≤ LT (v) + M η C i ln 1 p 1,i + K k=1 C k p 1,k -C i + 4M Cg K,J 3 ln 1 δ + 2 2g K,J ln 1 δ • LT (v).Recalling that, the solution of the following inequalityx -a √ x -b ≤ 0, x > 0, a > 0, b > 0, is x ≤ a 2 + b + a √ b. Solving for LT gives LT -LT (v) ≤ 2η g 3 K,J C ln 1 δ + 2 2g K,J C ln 1 δ 2 1 -η 1 + g K,J M 2 + 2η g 3 K,J C ln 1 δ + 2 2g K,J C ln 1 δ 1 -η 1 + g K,J M 3 2 • LT (v) + M η C i ln 1 p 1,i + K k=1 C k p 1,k -C i + 4M Cg K,J 3 ln 1 δ + 2 2g K,J ln 1 δ • LT (v)+ η 1 + g K,J M 1 -η 1 + g K,J M LT (v)+ M η C i ln 1 p1,i + K k=1 C k p 1,k -C i + 4M Cg K,J 3 ln 1 δ + 2 2g K,J ln 1 δ • LT (v) 1 -η 1 + g K,J M . Denote by A m = argmin i∈[K] C i .Let the learning rate and initial distribution p 1 satisfy η = ln (KT )2 1 + K-J (J-1)M T ∧ J -1 2(K -J) , p 1,k = 1 - √ K √ T 1 |A m | + 1 √ KT , k ∈ A m , p 1,j = 1 √ KT , j = A m .Then we haveC i ln 1 p 1,i + K k=1 C k p 1,k -C i ≤C i ln( √ KT ) + C • (K -|A m |) √ KT + min i C i • |A m | • 1 - √ K √ T 1 |A m | + 1 √ KT -C i ≤C i ln( √ KT ) + C √ K √ T .We further simplify LT -LT (v). LT -LT (v)≤64g K,J C ln 1 δ + 11 g K,J C ln 1 δ • C i T M + M η C i ln( √ KT ) + C √ K √ T + 4M Cg K,J 3 ln 1 δ + 2 2g K,J ln 1 δ • LT (v)+ 2η 1 + g K,J M C i T + M η C i ln( √ KT ) + C √ K √ T + 4M Cg K,J 3 ln 1 δ + 2C i 2g K,J ln 1 δ • √ T M 1 2 ≤ (64 + 3M )g K,J C ln 1 δ + 17 M g K,J CC i T ln 1 δ + 4 √ 2 C i M 1 + K -J (J -1)M T ln (KT ) Ξ4,5, in which we omit the lower order terms such as O(T 1 4 ) and O( g K,J C ln 1 δ ). Finally, the upper bound on Ξ 4,1 gives, with probability at leastEQUATION• ln 1 δ≤ LT -LT (v) + 2CM 3 ln 1 δ + 2 CM • LT (v) + Ξ 4,5 • ln 1 δ ≤(64 + 3M )g K,J C ln 1 δ + 17 M g K,J CC i T ln 1 δ + 4 √ 2 C i M 1 + K -J (J -1)M T ln (KT )+ 2M CC i T ln 1 δ ,where we omit O( CM Ξ 4,5 • ln 1 δ ) which is a lower order term.We also start with Lemma 1.We just a fixed i ∈ F i . We instantiate some notations.EQUATION.Lemma 1 gives∀w ∈ F i , 1 M T t=1 M j=1 f (j) t,i (x (j) t ), y (j) t -f (x (j) t ), y (j) t ≤ T t=1 D ψt,i (w, w t ) -D ψt (w, w t+1 ) + 1 2 T t=1 D ψt,i (w t , q t+1 )+ 1 2 T t=1 D ψt,i (w t , r t+1 ) + 1 M T t=1 M j=1 ∇(j) t,i -∇ (j) t,i , w t -w ,where the Bregman divergence isD ψt,i (w, v) = 1 2λ t,i w -v 2 2 .Besides, ( 13) and ( 14) can be instantiated as followsq t+1 =w t -λ t,i • 2 M M j=1 ∇(j) t,i -∇ (j) t,i , r t+1 =w t -λ t,i • 2 M M j=1 ∇ (j) t,i .Thus we have: ∀w ∈ F i ,1 M Ξ 5 ≤ T t=1 w -w t 2 2 -w -w t+1 2 2 2λ t,i + 2 T t=1 λ t,i 1 M M j=1 ∇(j) t,i -∇ (j) t,i 2 2 + 2 T t=1 λ t,i 1 M M j=1 ∇ (j) t,i 2 2 + 1 M T t=1 M j=1 ∇(j) t,i -∇ (j) t,i , w t -w ≤ 2U 2 i λ T,i + 2G 2 i T t=1 λ t,i + 2 T t=1 λ t,i M j=1 ∇(j) t,i -∇ (j) t,i M 2 2 Ξ5,1 + 1 M T t=1 M j=1 ∇(j) t,i -∇ (j) t,i , w t -w Ξ5,2.Next we separately give a high-probability upper bound on Ξ 4,1 and Ξ 4,2 .Bounding Ξ 5,2We define a random variable X t as follows,X t = 1 M M j=1 ∇(j) t,i -∇ (j) t,i , w t -w . X [T ] is a bounded martingale difference sequence w.r.t. H [T ] and |X t | ≤ 2g K,J G i U i . We further have T t=1 E t [|X t | 2 ] ≤ T t=1 4U 2 i E t    1 M M j=1 ∇(j) t,i -∇ (j) t,i 2 2    ≤ 4U 2 i G 2 i g K,J M T.The upper bound on the sum of conditional variance is a constant. Lemma 4 gives, with probability at least 1 -δ,Ξ 5,2 ≤ 4G i U i g K,J 3 ln 1 δ + 2G i U i 2 g K,J M T ln 1 δ . Bounding Ξ 5,1Recalling thatλ t,i =    Ui 2Gi (1+ g K,J M )•g 2 K,J if t ≤ g 2 K,J , Ui 2Gi (1+ g K,J M )•t otherwise.It can be found that λ t,i ≤ Ui 2g K,J Gi . Case 1: T > g 2 K,J . We decompose Ξ 5,1 as follows,Ξ 5,1 = g 2 K,J t=1 λ t,i 1 M M j=1 ∇(j) t,i -∇ (j) t,i 2 2 Ξ5,1,1 + T t=g 2 K,J +1 λ t,i 1 M M j=1 ∇(j) t,i -∇ (j) t,i 2 2 Ξ5,1,2.We separately analyze Ξ 5,1,1 and Ξ 5,1,2 . LetX t = λ t,i 1 M M j=1 ∇(j) t,i -∇ (j) t,i 2 2 -λ t,i E t    1 M M j=1 ∇(j) t,i -∇ (j) t,i 2 2    . X [T ] is a martingale difference sequence and satisfies |X t | ≤ λ t,i • g 2 K,J G 2 i ≤ g K,J UiGi 2. We further haveg 2 K,J t=1 E t [|X t | 2 ] ≤ g 2 K,J t=1 E t   λ 2 t,i 1 M M j=1 ∇(j) t,i -∇ (j) t,i 4 2    ≤ U 2 i G 2 i g 3 K,J 4M , T t=g 2 K,J +1 E t [|X t | 2 ] ≤U 2 i G 2 i g K,J 4M T -g 2 K,J .With probability at least 1 -2δ,Ξ 5,1 ≤ T t=1 λ t,i E t    1 M M j=1 ∇(j) t,i -∇ (j) t,i 2 2    + 2g K,J G i U i 3 ln 1 δ + G i U i 2 g K,J M T ln 1 δ ≤ g K,J M G 2 i T t=1 λ t,i + 2g K,J G i U i 3 ln 1 δ + G i U i 2 g K,J M T ln 1 δ .Combining with all results gives, with probability at leat 1 -3δ,1 M Ξ 5 ≤ 2U 2 i λ T,i + 2G 2 i 1 + g K,J M   g 2 K,J t=1 λ t,i + T t=g 2 K,J +1 λ t,i   + 2g K,J G i U i ln 1 δ + 3G i U i 2g K,J T M ln 1 δ ≤ 2U 2 i λ T,i + G i U i 1 + g K,J M g K,J + T t=g 2 K,J +1 1 √ t d t + 2g K,J G i U i ln 1 δ + 3G i U i 2g K,J T M ln 1 δ ≤6U i G i 1 + g K,J M T + 2g K,J G i U i ln 1 δ + 3G i U i 2g K,J T M ln 1 δ .Case 2: T ≤ g 2 K,J . In this case, we do not decompose Ξ 5,1 and λt,i = Ui 2Gi (1+ g K,J M )g 2 K,J. With probability at least1 -δ, Ξ 5,1 ≤ g K,J M G 2 i T t=1 λ t,i + g K,J G i U i 3 ln 1 δ + G i U i g K,J 2M T ln 1 δ .Furthermore, with probability at least 1 -2δ,1 M Ξ 5 ≤ 2U 2 i λ T,i + 2G 2 i 1 + g K,J M T t=1 λ t,i + 5g K,J G i U i 3 ln 1 δ + 4G i U i g K,J M T ln 1 δ ≤5U i G i 1 + g K,J M • g K,J + 5g K,J G i U i 3 ln 1 δ + 4G i U i g K,J M T ln 1 δ .Combining the two cases gives, with probability at least 1 -(M + 5)δ,1 M Ξ 5 ≤ 6U i G i 1 + g K,J M √ T + g K,J + 2g K,J G i U i ln 1 δ + 3G i U i 2g K,J M T ln 1 δ .Combining the upper bounds on Ξ 4 and Ξ 5 gives an upper bound on the regret. With probability at least 1 -Θ (M log(CT ) + log(CKT /M )) • δ,T t=1 M j=1 f (j) t,At,1 (x (j) t ), y (j) t - T t=1 M j=1 f (x (j) t ), y (j) t ≤M 1 + g K,J M 6U i G i √ T + g K,J + 4 √ 2 C i T ln (KT ) + (64C + 3M C + 2U i G i )g K,J ln 1 δ + (3 √ 2G i U i + 17 CC i ) 2M g K,J T ln 1 δ + 2M C i T ln 1 δ .Omitting the constant terms and lower order terms concludes the proof.We first establish a technical lemma.Lemma 5. Let X 1 , ..., X K be a sequence of independent standard normal random variables. LetZ K = max{X 1 , ..., X K }. If K ≥ 5, then E[Z K ] ≥ 1 -1 √ e √ 2 ln K.Proof of Lemma 5. Proposition 2.1.2 in Vershynin [2018] gives a lower bound on the tail probability of standard normal distribution.∀x > 0, P[X 1 ≥ x] = +∞ x 1 √ 2π exp - µ 2 2 d µ ≥ 1 √ 2π 1 x - 1 x 3 exp - x 2 2 .Then we haveE[Z K ] =E [Z K |∃i ∈ [K], X i ≥ ε] • P [∃i ∈ [K], X i ≥ ε] + E[Z K |∀X i < ε] • P [∀X i < ε] ≥P [∃i ∈ [K], X i ≥ ε] • ε = (1 -P [∀X i < ε]) • ε = 1 - K i=1 P [X i < ε] • ε = 1 - K i=1 (1 -P [X i ≥ ε]) • ε ≥ 1 -1 - 1 √ 2π 1 ε - 1 ε 3 exp - ε 2 2 K • ε. Let ε = √ 2 ln K. If K > 5, then we have 1 - 1 √ 2π 1 ε - 1 ε 3 exp - ε 2 2 K = 1 - 1 √ 2π 1 √ 2 ln K - 1 ln 1.5 K 2 1 K K ≤ 1 - 1 K 2 K ≤ 1 √ e .Substituting into the lower bound of E[Z K ] concludes the proof.J F i = {f i (x) = e i , x } , i = 1, 2, ..., K,where e i is the standard basis vector in R d . It is obvious that the time complexity of computingf i (x) = x i is O(1). At each client j, let the selected hypothesis be f (j) t and the prediction be f (j) t (x (j) t ). Since there are no computational constraints on each client, f (j) t (x (j) t ) can be a weighted combination of K predictions, i.e., f(j) t (x (j) t ) = K i=1 w (j) t,i f i (x (j) t ). The time complexity of computing f (j) t (x (j) t ) 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-Bianchi and Lugosi [2006] .Following the proof of Theorem 3.1 in Patel et al. [2023] , the adversary gives a sequence of same examples for each client. To be specific, we define x (j) t , y (j) t = (x t , y t ), t = 1, ..., T, j = 1, ..., M, where x t = (b t,1 , b t,2 , ..., b t,K , 0, . . . , 0) ∈ R d , and b t,1 , b t,2 , ..., b t,K , y t is a sequence of symmetric i.i.d. Bernoulli random variables, i.e., P[y t = 1] = P[y t = 0] = 1 2 . At any round t, the minimax regret against the best hypothesis can be simplified as followsinf f (1) 1 ,...,f (M ) T sup (x (j) t ,y (j) t ),,j∈[M ],t∈[T ] max i∈[K] Reg D (F i ) ≥ inf f (1) 1 ,...,f (M ) T sup (xt,yt),t∈[T ] max i∈[K] Reg D (F i ) ≥ inf f (1) 1 ,...,f (M ) T E (xt,yt),t∈[T ]   T t=1 M j=1 f (j) t (x t ), y t -min i∈[K] T t=1 M j=1 (f i (x t ), y t )   = inf f (1) 1 ,...,f (M ) T E (xt,yt),t∈[T ]   T t=1 M j=1 |f (j) t (x t ) -y t | -M min i∈[K] T t=1 |f i (x t ) -y t |   = M T 2 -M E (xt,yt),t∈[T ] min i∈[K] T t=1 |f i (x t ) -y t | =M E (xt,yt),t∈[T ] max i∈[K] T t=1 1 2 -f i (x t ) • (1 -2y t ) ,in which f i (x t ) = b t,i is a Bernoulli random variable andE (x,yt),t∈[T ]   T t=1 M j=1 |f (j) t (x t ) -y t |   = E yt,t∈[T ]   T t=1 M j=1 y t   = M T 2 .We further obtaininf f (1) 1 ,...,f (M ) T sup (x (j) t ,y (j) t ),j∈[M ],t∈[T ] max i∈[K] Reg D (F i ) ≥ M 2 E σt,Zt,i,t∈[T ],i∈[K] max i∈[K] T t=1 Z t,i • σ t = M 2 E Zt,i,t∈[T ],i∈[K] max i∈[K] T t=1 Z t,i ,where both {Z t,i } t∈[T ],i∈[K] and {σ t } t∈[T ] are i.i.d. Rademacher random variables.By Lemma A.11 in Cesa-Bianchi and Lugosi [2006] , we obtain limT →∞ E max i∈[K] 1 √ T T t=1 Z t,i = E max i∈[K] G i ,where G 1 , ..., G N are independent standard normal random variables.By Lemma 5, we obtain limT →∞ inf f (1) 1 ,...,f (M ) T sup (x (j) t ,y (j) t ),j∈[M ],t∈[T ] max i∈[K] Reg D (F i ) ≥ 1 2 1 - 1 √ e M √ 2T ln K,which concludes the proof.We mainly use the techniques in the proof of Theorem 2 in Seldin et al. [2014] , but also require a new technique. The idea of our proof is to reduce the online model selection on each client to multi-armed bandit problem with additional observations.Proof. Now we prove the second lower bound in Theorem 3.Let d ≥ K, X ⊆ R d and Y ∈ {0, 1}. We use a linear loss function (f (x t ), y t ) = 1 -y t f (x t ).Recalling that F i = {f i (x) = e i , x } , i = 1, 2, ..., K. It is obvious that the time complexity of computing f i (x) = x i is O(1). Under the constraint that the time complexity on each client is limited to O(J), on 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 ], f (j) t (x (j) t ) = i∈O (j) t w t,i f i (x (j) t ), where O (j) tcontains the index of selected J hypotheses by some algorithm. To address this challenge, we introduce a virtual strategy that randomly selects a hypothesis f (j) I (j) t ∈ {f At,1 , f At,2 , ..., f A t,J } following the distribution (w t,At,1 , w t,At,2 , ..., w t,A t,J ) where A t,a ∈ O (j) t , a = 1, ..., J. Since the loss function is a linear function, it is easy to prove that,EQUATIONwhere the expectation is taken over IEQUATIONt ) ≤ C for all i = 1, ..., K. Lemma A.7 in Cesa-Bianchi and Lugosi [2006] gives, with probability at least 1 -δ,T t=1 (f (j) I (j) t (x (j) t ), y (j) t ) -f (j) t (x (j) t ), y (j) t ≤ -C T 2 ln 1 δ .Note that we assume w t,i ≥ 0 and i∈O (j) t w t,i = 1 for all t = 1, ..., T . Recalling that Theorem 3 assumes the outputs of algorithm belong to [min i∈[K],x∈X f i (x), max i∈[K],x∈X f i (x)]. If w t,i < 0 or i∈O (j) tw t,i > 1, we can still find a weight vector w t,i ≥ 0 and i∈O (j)t w t,i = 1, such that f (j) t (x (j) t ) = i∈O (j) t w t,i f i (x (j) t ) = i∈O (j) t w t,i f i (x (j) t ).Then we sample I (j) t following (w t,At,1 , w t,At,2 , ..., w t,A t,J ).We can replace (w t,At,1 , w t,At,2 , ..., w t,A t,J ) with (w t,At,1 , w t,At,2 , ..., w t,A t,J ).Since the algorithm is non-cooperative, the total regret can be decomposed into the summation of the regret on each client. With probability at least 1EQUATIONNote that if we take expectation w.r.t. the randomness of algorithm, then the additional term 17) can be omitted following ( 16).C T 2 ln 1 δ in (If the prediction is not a combination of J predictions, but just f (j)EQUATIONCombining with the two cases, we just need to analyze Reg D (F i ).The adversary first uniformly samples a same h ∈ [K] for all clients, and then constructs {(x(j) t , y t )} T t=1 as follows x (j) t = x t := (b t,1 , b t,2 , ..., b t,K , 0, . . . , 0) , y (j) t = 1, j = 1, ..., M, in which b t,i satisfies P h [b t,i = 1] = 1 -ρ 2 , P h [b t,i = 0] = 1 + ρ 2 , i = h, P h [b t,h = 1] = 1 + ρ 2 , P h [b t,h = 0] = 1 -ρ 2 . Let E h [•] and P h [•]separately be the expectation and probability operator conditioned on h is selected. Then we haveP h [ (f i (x t ), 1) = 1] = 1 + ρ 2 , P h [ (f i (x t ), 1) = 0] = 1 -ρ 2 , i = h, P h [ (f h (x t ), 1) = 1] = 1 -ρ 2 , P h [ (f h (x t ), 1) = 0] = 1 + ρ 2 .It is obvious that online model selection can be reduced to a K-armed bandit problem, in which f i is the i-th arm. At each round t, let I (j) t be the selected arm. Besides, any algorithm can select another J -1 arms. Thus any algorithm can observe J losses. Let O (j) t be the set of the selected J arms. Note that f (j)I (j) t = f I (j) t for any I (j) t ∈ [K].Assuming that the algorithm is deterministic, that is, O (j) t is determined by {O I (j) t (x t ), 1 -min i∈[K] T t=1 (f i (x t ), 1) ≥E h T t=1 f (j) I (j) t (x t ), 1 -min i∈[K] E h T t=1 (f i (x t ), 1) =ρ • E h T t=1 I I (j) t =h =ρT • 1 - 1 T E h [N T,h ] .Following the techniques in the proof of Theorem 2 in Seldin et al. [2014] , we haveEQUATIONFor any deterministic algorithm, we can provesup (x (j) t ,y (j) t ),t∈[T ],j∈[M ] max i∈[K] Reg D (F i ) ≥ sup (xt,1),t∈[T ],h∈[K]   T t=1 M j=1 f (j) t (x t ), 1 -min i∈[K] T t=1 M j=1 (f i (x t ), 1)   = sup (xt,1),t∈[T ],h∈[K]   T t=1 M j=1 f (j) t (x t ), 1 -M min i∈[K] T t=1 (f i (x t ), 1)   ≥ sup h∈[K] E h xt,t∈[T ]   M j=1 T t=1 f (j) I (j) t (x t ), 1 -min i∈[K] T t=1 (f i (x t ), 1)   ≥ sup h∈[K] M j=1 E h xt,t∈[T ] T t=1 f (j) I (j) t (x t ), 1 -min i∈[K] E h xt,t∈[T ] T t=1 (f i (x t ), 1) ≥ E h∈[K] M j=1 E h T t=1 f (j) I (j) t (x t ), 1 -min i∈[K] E h T t=1 (f i (x t ), 1) = M j=1 1 K K h=1 E h T t=1 f (j) I (j) t (x t ), 1 -min i∈[K] E h T t=1 (f i (x t ), 1) ≥0.1M K J T , Algorithm 4 NCO-OMS Require: T , J, η1, {Ui, λ1,i, i ∈ [K]} Ensure: f (j) 1,i = 0, p1,i, i ∈ [K], j ∈ [M ] 1: for t = 1, 2, . . . , T do 2:for j = 1, . . . , M do 3:The client samples O (j) t following (7) 4:The client outputs f(j) t,A t,1 (x (j) t ) 5:The client computes fEQUATIONt ) for all a = 2, . . . , J 6:The client computes ∇(j) t,i and c(j) t,i for all i ∈ O (j) tThe client computes p end for 9: end for where the last inequality comes from (19). As claimed in the proof of Theorem 6.11 in Cesa-Bianchi and Lugosi [2006] , the lower bound of any randomized algorithm is same with that of any deterministic algorithm, i.e., sup (x(j) t ,y (j) t ),t∈[T ],j∈[M ] E max i∈[K] Reg D (F i ) = sup (x (j) t ,y (j) t ),t∈[T ],j∈[M ] E T t=1 f (j) I (j) t (x (j) t ), y (j) t -min i∈[K] T t=1 f i (x (j) t ), y (j) t ≥0.1M √ KT √ J ,in which the expectation is taken over the internal randomness of algorithm. Substituting into (17), or (18) concludes the proof.Algorithm 4 gives the pseudo-code of NCO-OMS.Following the definition of NCO-OMS and Algorithm 4, it is obvious that the regret bound of NCO-OMS on each client is same with Theorem 2 in which we set M = 1. The regret bound on M clients is M times of that of a client. Thus we have Theorem 6. Theorem 6 (Regret Bound of NCO-OMS). Let the learning rate η, λ t,i and the initial distribution p 1 be same for each client j ∈ [M ]. The values of η, λ t,i and p 1 follow Theorem 2 in which M = 1. With probability at least 1 -Θ (M log(KT )) • δ, the regret of NCO-OMS satisfies:∀i∈ [K], Reg D (F i ) = O M B i,1 (1 + g K,J ) T + B i,2 g K,J ln 1 δ + B i,3 g K,J T ln 1 δ , where B i,1 = U i G i + C i ln(KT ), B i,2 = C + U i G i and B i,3 = U i G i + √ CC i and C = max i C i .L Proof of Theorem 4We give the pseudo-code in Algorithm 5.To implement Algorithm 5, we require one more technique, i.e., the random features [Rahimi and For any i ∈ [K], we consider the kernel function κ i (x, v) that has an integral representation, i.e.,EQUATIONwhere ϕ i : X × Γ → R is the eigenfunctions and µ i (•) is a distribution function on Γ. Let p i (•) be the density function of µ i (•). We sample {ω j } D j=1 ∼ p i (ω) independently and compute κi (x, v) = 1 D D j=1 ϕ i (x, ω j )ϕ i (v, ω j ).For any f (x) = Γ α(ω)ϕ i (x, ω)p i (ω)d ω.We can approximate f (x) by f (x) = 1 D D j=1 α(ω j )ϕ i (x, ω j ). It can be verified that E[ f (x)] = f (x). Such an approximation scheme also defines an explicit feature mapping denoted by φ i (x) = 1 √ D (ϕ i (x, ω 1 ), . . . , ϕ i (x, ω D )) .For each κ i , i ∈ [K], we define two hypothesis spaces [Rahimi and Recht, 2008, Li and Liao, 2022] as followsEQUATIONin which F i is exact the hypothesis space defined in (1).It can be verified that w 2 2 ≤ U 2 i . Let W i = {w ∈ R D : w ∞ ≤ Ui √ D }. We replace (9) with ( 22),                ∇ wt+1,i ψ t,i ( wt+1,i ) =∇ wt,i ψ t,i (w t,i ) -1 M M j=1 ∇(j) t,i , i = 1, ..., K, w t+1,i = arg min w∈Wi D ψt,i (w, wt+1,i ),ψ t,i (w) = 1 2λ t,i• w 2 2 .(22)We first give an assumption and a technique lemma.Assumption 2 (Li et al. [2019] ). For any i ∈ [K], if κ i satisfies (20), then there is a bounded constant b i such that, ∀x ∈ X , The lemma is adopted from Lemma 5 in [Li and Liao, 2023] . Thus we omit the proof. Now we begin to prove Theorem 4. Reg D (H i ) is the regret that we run FOMD-OKS with hypothesis spaces {H i } K i=1 . f ∈ H i satisfies Lemma 6. In other words, Ξ 6 is induced by the approximation error that we use f to approximate f . Reg D (H i ) has been given by Theorem 5. Next we analyze Ξ 6 .Using the convexity of (•, •), with probability at least 1 -T M δ, • f (x(j) t ) -f (x (j) t ) ≤g i b i U i M T √ D 2 ln 1 δ ≤G i U i M T √ D 2 ln 1 δ .Under Assumption 2, there is a constant g i such that Combining the upper bounds on Reg D (H i ) and Ξ 6 concludes the proof.•The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at 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 run 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 or the standard error of the mean. 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 a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or 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]• 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.https://archive.ics.uci.edu/ml/index.phpThe code of algorithms is available at https://github.com/JunfLi-TJU/OMS-DecD.gitRecht, 2007]. We will use the 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 is that we can avoid the O(T ) computational cost on the clients. 


Decision: 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.

Reviews: review: paper_summary: paper_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. 
The 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.
strength_weakness: strength_weakness: 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.
questions: questions: Addressed in the previous section. 
Additionally 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: limitations: No specific limitations.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: 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: Limitations adequately discussed.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
2. 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.
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.
3. 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.
questions: questions: Please see the weaknesses part.

Question 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: limitations: The authors have adequately addressed the limitations and societal impact.
paper_summary: paper_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$).
strength_weakness: strength_weakness: I didn't see any significant weaknesses.
questions: questions: N/A
limitations: limitations: N/A

Comments: comment: Thank you for taking the time to provide feedback on our response. We are pleased that our reply has addressed your concerns. We also appreciate your positive evaluation of our contributions.
Thanks for the detailed responses. The discussion on motivation and communication costs in the responses is helpful in deepening the understanding of this work. A detailed discussion of the related works also makes the contribution of this work clearer. Overall, I will raise my score to $5$ since the rebuttal addresses my concerns.