Federated Online Prediction from Experts with Differential Privacy: Separations and Regret Speed-ups

Authors: fengyu  gao
ruiquan  huang
jing  yang
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 17:11:58

Abstract: We study the problems of differentially private federated online prediction from experts against both *stochastic adversaries* and *oblivious adversaries*. We aim to minimize the average regret on $m$ clients working in parallel over time horizon $T$ with explicit differential privacy (DP) guarantees. With stochastic adversaries, we propose a **Fed-DP-OPE-Stoch** algorithm that achieves $\sqrt{m}$-fold speed-up of the per-client regret compared to the single-player counterparts under both pure DP and approximate DP constraints, while maintaining logarithmic communication costs. With oblivious adversaries, we establish non-trivial lower bounds indicating that *collaboration among clients does not lead to regret speed-up with general oblivious adversaries*. We then consider a special case of the oblivious adversaries setting, where there exists a low-loss expert. We design a new algorithm **Fed-SVT** and show that it achieves an $m$-fold regret speed-up under both pure DP and approximate DP constraints over the single-player counterparts. Our lower bound indicates that Fed-SVT is nearly optimal up to logarithmic factors. Experiments demonstrate the effectiveness of our proposed algorithms. To the best of our knowledge, this is the first work examining the differentially private online prediction from experts in the federated setting.

Main paper: 
 introduction: 
 Federated Learning (FL) (McMahan et al., 2017) is a distributed machine learning framework, where numerous clients collaboratively train a model by exchanging model update through a server. Owing to its advantage in protecting the privacy of local data and reducing communication overheads, FL is gaining increased attention in the research community, particularly in the online learning framework (Mitra et al., 2021; Park et al., 2022; Kwon et al., 2023; Gauthier et al., 2023) . Noticeable advancements include various algorithms in federated multi-armed bandits (Shi et al., 2021; Huang et al., 2021; Li and Wang, 2022; Yi and Vojnovic, 2022, 2023) , federated online convex optimization (Patel et al., 2023; Kwon et al., 2023; Gauthier et al., 2023) , etc.Meanwhile, differential privacy (DP) has been integrated into online learning, pioneered by Dwork et al. (2010) . Recently, Asi et al. (2022b) studied different types of adversaries, developing some of the best existing algorithms and establishing lower bounds. Within the federated framework, although differentially private algorithms have been proposed for stochastic bandits (Li et al., 2020b; Zhu et al., 2021; Dubey and Pentland, 2022) and linear contextual bandits (Dubey and Pentland, 2020; Li et al., 2022a; Zhou and Chowdhury, 2023; Huang et al., 2023) , to the best of our knowledge, federated online learning in the adversarial setting with DP considerations remain largely unexplored.In this work, we focus on federated online prediction from experts (OPE) with rigorous differential privacy (DP) guarantees1 . OPE (Arora et al., 2012) is a classical online learning problem under which, a player chooses one out of a set of experts at each time slot and an adversary chooses a loss function. The player incurs a loss based on its choice and observes the loss function. With all previous observations, the player needs to decide which expert to select each time to minimize the cumulative expected loss. We consider two types of adversaries in the context of OPE. The first type, stochastic adversary, chooses a distribution over loss functions and samples a loss function independently and identically distributed (IID) from this distribution at each time step. The second type, oblivious adversary, chooses a sequence of loss functions in advance. 2When extending the OPE problem to the federated setting, we assume that the system consists of a central server and m local clients, where each client chooses from d experts to face an adversary at each time step over time horizon T . The server coordinates the behavior of the clients by aggregating the clients' updates to form a global update (predicting a new global expert), while the clients use the global expert prediction to update its local expert selection and compute local updates. The local updates will be sent to the server periodically. In the Federated OPE framework, clients face either stochastic adversaries, receiving loss functions from the same distribution in an IID fashion, or oblivious adversaries, which arbitrarily select loss functions for each client at each time step beforehand (Yi and Vojnovic, 2023) . Specifically, we aim to answer the following question:Can we design differentially private federated OPE algorithms to achieve regret speed-up against both stochastic and oblivious adversaries?In this paper, we give definitive answers to the question. Our contributions are summarized as follows.• Speed-up for stochastic adversaries. We develop a communication-efficient algorithm Fed-DP-OPE-Stoch for stochastic adversaries with DP guarantees. The algorithm features the following elements in its design: 1) Local loss function gradient estimation for global expert determination.To reduce communication cost, we propose to estimate the gradient of each client's previous loss functions locally, and only communicate these estimates to the server instead of all previous loss functions. 2) Local privatization process. Motivated by the need for private communication in FL, we add noise to client communications (local gradient estimates) adhering to the DP principles, thereby building differentially private algorithms. We show that Fed-DP-OPE-Stoch achieves 1/ √ m-fold reduction of the per-client regret compared to the single-player counterparts (Asi et al., 2022b) under both pure DP and approximate DP constraints, while maintaining logarithmic communication costs.• Lower bounds for oblivious adversaries. We establish new lower bounds for federated OPE with oblivious adversaries. Our findings reveal a critical insight: collaboration among clients does not lead to regret speed-up in this context. Moreover, these lower bounds highlight a separation between oblivious adversaries and stochastic adversaries, as the latter is necessary to reap the benefits of collaboration in this framework. Formulating an instance of oblivious adversaries for the corresponding lower bounds is a non-trivial challenge, because it requires envisioning a scenario where the collaborative nature of FL does not lead to the expected improvements in regret minimization. To deal with this challenge, we propose a policy reduction approach in FL. By defining an "average policy" among all clients against a uniform loss function generated by an oblivious adversary, we reduce the federated problem to a single-player one, highlighting the equivalence of per-client and single-player regret. Our lower bounds represent the first of their kind for differentially private federated OPE problems.• Speed-up for oblivious adversaries under realizability assumption. We design a new algorithm Fed-SVT that obtains near-optimal regret when there is a low-loss expert. We show that Fed-SVT achieves an m-fold speed-up in per-client regret when compared to single-player models (Asi et al., 2023) . This shows a clear separation from the general setting where collaboration among clients does not yield benefits in regret reduction when facing oblivious adversaries. Furthermore, we establish a new lower bound in the realizable case. This underlines that our upper bound is nearly optimal up to logarithmic factors. (Asi et al., 2022b) A summary of our main results and how they compare with the state of the art is shown in Table 1 . A comprehensive literature review is provided in Appendix A.Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?Answer: [Yes] Justification: See the abstract and introduction.Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in 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 or 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. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
preliminaries: 
 Federated online prediction from experts. Federated OPE consists of a central server, m clients and an interactive T -round game between an adversary and an algorithm. At time step t,each client i ∈ [m] first selects an expert x i,t ∈ [d],and then, the adversary releases a loss function l i,t . Stochastic adversaries choose a distribution over loss functions and sample a sequence of loss functions l 1,1 , . . . , l m,T in an IID fashion from this distribution, while oblivious adversaries choose a sequence of loss functions l 1,1 , . . . , l m,T at the beginning of the game.For federated OPE, the utility of primary interest is the expected cumulative regret among all clients defined as:Reg(T, m) = 1 m m i=1 T t=1 l i,t (x i,t ) -min x ⋆ ∈[d] m i=1 T t=1 l i,t (x ⋆ ) .Differential privacy. We define differential privacy in the online setting following (Dwork et al., 2010) . If an adversary chooses a loss sequence S = (l 1,1 , . . . , l m,T ), we denote A(S) = (x 1,1 , . . . , x m,T ) the output of the interaction between the federated online algorithm A and the adversary. We say S = (l 1,1 , . . . , l m,T ) and S ′ = l ′ 1,1 , . . . , l ′ m,T are neighboring datasets if S and S ′ differ in a one element. 3 . Definition 1 ((ε, δ)-DP). A randomized federated algorithm A is (ε, δ)-differentially private against an adversary if, for all neighboring datasets S and S ′ and for all events O in the output space of A, we haveP[A(S) ∈ O] ≤ e ε P [A (S ′ ) ∈ O] + δ.Communication model. Our setup involves a central server facilitating periodic communication with zero latency with all clients. Specifically, the clients can send "local model updates" to the central server, which then aggregates and broadcasts the updated "global model" to the clients. We assume full synchronization between clients and the server (McMahan et al., 2017) . Following Wang et al. (2019) , we define the communication cost of an algorithm as the number of scalars (integers or real numbers) communicated between the server and clients.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification: See Section 7.Guidelines:• The answer NA means that the paper has no 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 a 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 (e.g., independence assumptions, noiseless settings, model well-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 a few datasets or with a 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to 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 fairness. • 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 acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
federated ope with stochastic adversaries: 
 In this section, we aim to design an algorithm for Fed-DP-OPE with stochastic adversaries that achieves regret speed-up compared to the single-player setting under DP constraints with lowIn the federated setting, it is infeasible for the central server to have full access to past loss functions due to the high communication cost. To overcome this, we use a design of local loss function gradient estimation for global expert determination. Our solution involves locally estimating the gradient of each client's loss functions, and then communicating these estimates to the server, which globally generates a new prediction. This strategy bypasses the need for full access to all loss functions, reducing the communication overhead while maintaining efficient expert selection.To enhance privacy in the federated system, we implement a local privatization process. When communication is triggered, clients send "local estimates" of the gradients of their loss functions to the server. These local estimates include strategically added noise, adhering to DP principles. The privatization method is crucial as it extends beyond privatizing the selection of experts; it ensures the privacy of all information exchanged between the central server and clients within the FL framework.To address the aforementioned challenges, we propose the Fed-DP-OPE-Stoch algorithm. The Fed-DP-OPE-Stoch algorithm works in phases. In total, it has P phases, and each phase p ∈ [P ] contains 2 p-1 time indices. Fed-DP-OPE-Stoch contains a client-side subroutine (Algorithm 1) and a server-side subroutine (Algorithm 2). The framework of our algorithm is outlined as follows.At the initialization phase, the server selects an arbitrary point z ∈ X and broadcasts to all clients. Subsequently, each client initializes its expert selection x i,1 = z, pays cost l i,1 (x i,1 ) and observes the loss function.Starting at phase p = 2, each client uses loss functions from the last phase to update its local loss function gradient estimation, and then coordinates with the server to update its expert selection. After that, it sticks with its decision throughout the current phase and observes the loss functions. We elaborate this procedure as follows.Private Local Loss Function Gradient Estimation. At the beginning of phase p, each client privately estimates the gradient using local loss functions from the last phase B i,p = {l i,2 p-2 , . . . , l i,2 p-1 -1 }.We employ the tree mechanism for the private aggregation at each client, as in the DP-FW algorithm from Asi et al. (2021b) . Roughly speaking, DP-FW involves constructing binary trees and allocating sets of loss functions to each vertex. The gradient at each vertex is then estimated using the loss functions of that vertex and the gradients along the path to the root. Specifically, we run a DP-FW subroutine at each client i, with sample set B i,p , parameter T 1 and batch size b. In DP-FW, each vertex s in the binary tree j corresponds to a gradient estimate v i,j,s . DP-FW iteratively updates gradient estimates by visiting the vertices of binary trees. The details of DP-FW can be found in Algorithm 3 in Appendix C.1.Intuitively, in the DP-FW subroutine, reaching a leaf vertex marks the completion of gradient refinement for a specific tree path. At these critical points, we initiate communication between the central server and individual clients. Specifically, as the DP-FW subroutine reaches a leaf vertex s of tree j, each client sends the server a set of noisy inner products for each decision set vertex c n with their gradient estimate v i,j,s . In other words, each client communicates with the server by sending {⟨c n , v i,j,s ⟩ + ξ i,n } n∈ [d] , where c 1 , . . . , c d represents d vertices of decision set X = ∆ d , ξ i,n ∼ Lap(λ i,j,s ), and λ i,j,s = 4α2 j bε . Private Global Expert Prediction. After receiving {⟨c n , v i,j,s ⟩ + ξ i,n } n∈ [d] from all clients, the central server privately predicts a new expert:wj,s = arg min cn:1≤n≤d 1 m m i=1 ⟨c n , v i,j,s ⟩ + ξ i,n .(1)Subsequently, the server broadcasts the "global prediction" wj,s to all clients.Local Expert Selection Updating. Denote the index of the leaf s of tree j as k. Then, upon receiving the global expert selection wj,s , each client i updates its expert prediction for leaf k + 1, denoted as x i,p,k+1 ∈ X , as follows:EQUATIONwhere η i,p,k = 2 k+1 . After updating all leaf vertices of the trees, the client obtains x i,p,K , the final state of the expert prediction in phase p. Then, each client i sticks with expert selection x i,p,K throughout phase p and collects loss functions l i,2 p-1 , . . . , l i,2 p -1 . Remark 1 (Comparison with Asi et al. (2022b) ). The key difference between Fed-DP-OPE-Stoch and non-federated algorithms (Asi et al., 2022b) lies in our innovative approach to centralized coordination and communication efficiency. Unlike the direct application of DP-FW in each phase in Asi et al. (2022b) , our algorithm employs local loss function gradient estimation, global expert prediction and local expert selection updating. Additionally, our strategic communication protocol, where clients communicate with the server only when DP-FW subroutine reaches leaf vertices, significantly reduces communication costs. Moreover, the integration of DP at the local level in our algorithm distinguishes it from non-federated approaches.Algorithm 1 Fed-DP-OPE-Stoch: Client i 1: Input: Phases P , trees T 1 , decision set X = ∆ d with vertices {c 1 , . . . , c d }, batch size b. 2: Initialize: Set x i,1 = z ∈ X and pay cost l i,1 (x i,1 ). 3: for p = 2 to P do 4:Set B i,p = {l i,2 p-2 , . . . , l i,2 p-1 -1 } 5:Set k = 1 and x i,p,1 = x i,p-1,K 6:{v i,j,s } j∈[T1],s∈{0,1} ≤j = DP-FW (B i,p , T 1 , b) 7:for all leaf vertices s reached in DP-FW do 8:Communicate to server: {⟨c n , v i,j,s ⟩ + ξ i,n } n∈ [d] , where ξ i,n ∼ Lap(λ i,j,s )Receive from server: wj,s Final iterate outputs x i,p,K 14:for t = 2 p-1 to 2 p -1 do 15:Receive loss l i,t : X → R and pay cost l i,t (x i,p,K ) 16:end for 17: end forNow we are ready to present theoretical guarantees for Fed-DP-OPE-Stoch. Theorem 1. Assume that loss function l A similar result characterizing the performance of Fed-DP-OPE-Stoch under (ε, δ)-DP constraint is shown in Theorem 6.i,t (•) is convex, α-Lipschitz, β-smooth w.r.t. ∥ • ∥ 1 . Setting λ i,j,s = 4α2 j bε , b = 2 p-1 (p-1) 2 and T 1 = 1 2 log bεβ √ m α log d ,Proof sketch of DP guarantees and communication costs. Given neighboring datasets S and S ′ differing in l i1,t1 or l ′ i1,t1 , we first note that l i1,t1 or l ′ i1,t1 is used in only one phase, denoted as p 1 . Furthermore, note that l i1,t1 or l ′ i1,t1 is used in the gradient computation for at most 2 j-|s| iterations, corresponding to descendant leaf nodes. This insight allows us to set noise levels λ i,j,s sufficiently large to ensure each of these iterations is ε/2 j-|s| -DP regarding output {⟨c n , v i1,j,s ⟩} n∈ [d] ,j∈[T1],|s|=j . By basic composition and post-processing, we can make sure the final output is ε-DP.The communication cost is obtained by observing that there are p phases, and within each phase, there are O(2 T1 ) leaf vertices. Thus, the communication frequency scales in O( p 2 T1 ) and the communication cost scales in O(md p 2 T1 ).Proof sketch of regret upper bound. We first give bounds for the total regret in phase p ∈ [P ]. We can show that for every t in phase p, we haveL t (x i,p,k+1 ) ≤ L t (x i,p,k ) + η i,p,k [L t (x ⋆ ) -L t (x i,p,k )] + η i,p,k ∥∇L t (x i,p,k ) -vp,k ∥ ∞ + η i,p,k ⟨v p,k , wp,k ⟩ -min w∈X ⟨v p,k , w⟩ + 1 2 βη i,p,k 2 .To upper bound the regret, we bound the following two quantities separately.Step 1: bound ∥∇L t (x i,p,k ) -vp,k ∥ ∞ in Lemma 3. We show that every index of the d-dimensionalvector ∇L t (x i,p,k )-vp,k is O( α 2 +β 2 bm )-sub-Gaussian by induction on the depth of vertex in Lemma 2. Therefore, E [∥∇L t (x i,p,k ) -vp,k ∥ ∞ ] is upper bounded by O (α + β) log d bm .Step 2: bound ⟨v p,k , wp,k ⟩ -min w∈X ⟨v p,k , w⟩ in Lemma 5. We establish that ⟨v p,k , wp,k ⟩ - ). This observation underscores the learning performance acceleration due to collaboration. Furthermore, our approach extends beyond the mere privatization of selected experts; we ensure the privacy of all information exchanged between the central server and clients. Remark 3. We remark that Fed-DP-OPE-Stoch can be slightly modified into a centrally differentially private algorithm, assuming client-server communication is secure. Specifically, we change the local privatization process to a global privatization process on the server side. This mechanism results in less noise added and thus better utility performance. The detailed design is deferred to Appendix C.4 and the theoretical guarantees are provided in Theorem 7.min w∈X ⟨v p,k ,Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer: [Yes]• It 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 a 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 of range (e.g. negative error rates). 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] Justification: See Appendix G. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment 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 to particular applications, let alone deployments. However, if there is a 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 
federated ope with oblivious adversaries: lower bounds: 
 In this section, we shift our attention to the more challenging oblivious adversaries. We establish new lower bounds for general oblivious adversaries.To provide a foundational understanding, we start with some intuition behind FL. FL can potentially speed up the learning process by collecting more data at the same time to gain better insights to future predictions. In the stochastic setting, the advantage of collaboration lies in the ability to collect more observations from the same distribution, which leads to variance reduction. However, when facing oblivious adversaries, the problem changes fundamentally. Oblivious adversaries can select loss functions arbitrarily, meaning that having more data does not necessarily help with predicting their future selections.The following theorem formally establishes the aforementioned intuition. Theorem 2. For any federated OPE algorithm against oblivious adversaries, the per-client regret is lower bounded by Ω( √ T log d). Let ε ∈ (0, 1] and δ = o(1/T ), for any (ε, δ)-DP federated OPE algorithm, the per-client regret is lower bounded by Ω min log d ε , T . Remark 4. Theorem 2 states that with oblivious adversaries, the per-client regret under any federated OPE is fundamentally independent of the number of clients m, indicating that, the collaborative effort among multiple clients does not yield a reduction in the regret lower bound. This is contrary to typical scenarios where collaboration can lead to shared insights and improve overall performance. The varied and unpredictable nature of oblivious adversaries nullifies the typical advantages of collaboration. Theorem 2 also emphasizes the influence of the DP guarantees. Our lower bounds represent the first non-trivial impossibility results for the federated OPE to the best of our knowledge.Proof sketch. We examine the case when all clients receive the same loss function from the oblivious adversary at each time step, i.e. l i,t = l ′ t . Within this framework, we define the "average policy" among all clients, i.e., p ′t (k) = 1 m m i=1 p i,t (k), ∀k ∈ [d].This leads us to express the per-client regret as:Reg(T, m) = T t=1 d k=1 p ′ t (k) • l ′ t (k) - T t=1 l ′ t (x ⋆ ). Note that p ′ t (k) is defined by p 1,t (k), . . . , p m,t (k), which in turn are determined by l 1,1 , . . . , l m,t-1 . According to our choice of l i,t = l ′ t , p ′ t (k) is determined by l ′ 1 , l ′ 2 , . . . , l ′ t-1 . Therefore, p ′ 1 , p ′ 2 , .. . , p ′ t are generated by a legitimate algorithm for online learning with expert advice problems. Through our policy reduction approach in FL, we can reduce the federated problem to a single-player setting, showing the equivalence of per-client and single-player regret against the oblivious adversary we construct, thus obtaining the regret lower bound. We believe that this technique will be useful in future analysis of other FL algorithm. Incorporating DP constraints, we refer to Lemma 9, which transforms the DP online learning problem to a well-examined DP batch model. The full proof of Theorem 2 can be found in Appendix D. 
federated ope with oblivious adversaries: realizable setting: 
 Given the impossibility results in the general oblivious adversaries setting, one natural question we aim to answer is, is there any special scenarios where we can still harness the power of federation even in presence of oblivious adversaries? Towards this end, in this section, we focus on the (near) realizable setting, formally defined below. Definition 2 (Realizability). A federated OPE problem is realizable if there exists a feasible solutionx ⋆ ∈ [d] such that T t=1 l i,t (x ⋆ ) = 0, ∀i ∈ [m]. If the best expert achieves small loss L ⋆ ≪ T , i.e., there exists x ⋆ ∈ [d] such that T t=1 l i,t (x ⋆ ) ≤ L ⋆ , ∀i ∈ [m], the problem is near-realizable.Intuitively, collaboration is notably advantageous in this context, as all clients share the same goal of reaching the zero-loss solution x ⋆ . As more clients participate, the shared knowledge pool expands, making the identification of the optimal solution more efficient. In the following, we first provide regret lower bounds to quantify this benefit formally, and then show that a sparse vector based federated algorithm can almost achieve such lower bounds thus is nearly optimal.Theorem 3. Let ε ≤ 1 and δ ≤ ε/d. For any (ε, δ)-DP federated OPE algorithm against oblivious adversaries in the realizable setting, the per-client regret is lower bounded by Ω log(d) mε .Remark 5. In the single-player setting, the regret bound is Ω log(d) ε (Asi et al., 2023) . In the federated setting, our results imply that the per-client regret is reduced to 1 m times the single-player regret. This indicates a possible m-fold speed-up in the federated setting.Proof sketch. To begin, we consider a specific oblivious adversary. We introduce two prototype loss functions: l 0 (x) = 0 for all x ∈ [d] and for j ∈ [d] l j (x) = 0 if x = j and otherwise l j (x) = 1. An oblivious adversary picks one of the d sequences S 1 , . . . , S d uniformly at random, where S j = (l j 1,1 , . . . , l j m,T ) such that l j i,t = l 0 if t = 1, . . . , T -k, otherwise, l j i,t = l j , and k = log d 2mε . Assume there exists an algorithm such that the per-client regret is upper bounded by log(d) 32mε . This would imply that for at least d/2 of S 1 , . . . , S d , the per-client regret is upper bounded by log(d) 16mε . Assume without loss of generality these sequences are S 1 , . . . , S d/2 . We let B j be the set of expert selections that has low regret on S j . We can show that B j and B j ′ are disjoint for j ̸ = j ′ , implying choosing any expert j leads to low regret for loss sequence S j but high regret for S j ′. By group privacy, we have P A S j ∈ B j ′ ≥ e -mkε P A S j ′ ∈ B j ′ -mkδ, leading to a contradiction when d ≥ 32. The full proof of Theorem 3 can be found in Appendix E.1.We develop a new algorithm Fed-SVT. Our algorithm operates as follows:Periodic communication. We adopt a fixed communication schedule in our federated setting, splitting the time horizon T into T /N phases, each with length N . In Fed-SVT, every client selects the same expert, i.e., x i,t = x t at each time step t. Initially, each client starts with a randomly chosen expert x 1 . At the beginning of each phase n, each client sends the accumulated loss of the last phase nN -1 t ′ =(n-1)N l i,t ′ (x) to the central server.nN -1 t ′ =(n-1)N l i,t ′ (x) from all clients, decides whether to continue with the current expert or switch to a new one. This decision is grounded in the Sparse-Vector algorithm (Asi et al., 2023) , where the accumulated loss from all clients over a phase is treated as a single loss instance in the Sparse-Vector algorithm. Based on the server's expert decision, clients update their experts accordingly. The full algorithm is provided in Appendix E.2.Theorem 4. Let l i,t ∈ [0, 1] d be chosen by an oblivious adversary under nearrealizability assumption. Fed-SVT is ε-DP, the communication cost scales in O (mdT /N ), and with probability at least 1 -O(ρ), the pre-client regret is upper bounded by Fed-SVT. We conduct experiments in a synthetic environment, comparing Fed-SVT with the single-player model Sparse-Vector (Asi et al., 2023) .O log 2 (d)+log T 2 N 2 ρ log( d ρ ) mε + (N + L ⋆ ) log d ρ . Moreover, Fed-SVT is (ε, δ)- 
numerical experiments: 
 We generate random losses for each expert at every timestep and for each client, ensuring that one expert always has zero loss to simulate an optimal choice. We set m = 10, T = 2 9 , ε = 10, δ = 0 and d = 100. In Fed-SVT, we experiment with communication intervals N = 1, 30, 50, where communication cost scales in O(mdT /N ). The per-client cumulative regret as a function of T is plotted in Figure 2 . Our results show that Fed-SVT significantly outperforms the Sparse-Vector, highlighting the benefits of collaborative expert selection in regret speed-up, even at lower communication costs (notably in the N = 50 case). Results with different seeds are provided in Appendix F. Additionally, we evaluate the performances of Fed-SVT on the MovieLens-1M dataset (Harper and Konstan, 2015) in Appendix G. 
conclusions: 
 In this paper, we have advanced the state-of-the-art of differentially private federated online prediction from experts, addressing both stochastic and oblivious adversaries. Our Fed-DP-OPE-Stoch algorithm showcases a significant √ m-fold regret speed-up compared to single-player models with stochastic adversaries, while effectively maintaining logarithmic communication costs. For oblivious adversaries, we established non-trivial lower bounds, highlighting the limited benefits of client collaboration. Additionally, our Fed-SVT algorithm demonstrates an m-fold speed-up, indicating near-optimal performance in settings with low-loss experts. One limitation of this work is the lack of experiments on real-world federated learning scenarios such as recommender systems and healthcare. We leave this exploration to future work. 
 
 Appendix: Online learning with stochastic adversaries. Online learning with stochastic adversaries has been extensively studied (Rakhlin et al., 2011; Duchi et al., 2011; Hu et al., 2009; Li et al., 2020a; Caron et al., 2012; Buccapatnam et al., 2014; Tossou et al., 2017; Wu et al., 2015) . This problem is also closely related to stochastic convex optimization (Shalev-Shwartz et al., 2009; Mahdavi et al., 2013; Duchi et al., 2015; Agarwal et al., 2011; Duchi et al., 2016) since online learning with stochastic adversaries can be transformed into the stochastic convex optimization problem using online-tobatch conversion. In the federated setting, Mitra et al. (2021) proposed a federated online mirror descent method. Patel et al. (2023) presented a federated projected online stochastic gradient descent algorithm. Research on online learning with stochastic adversaries incorporating DP has also seen significant advancements (Bassily et al., 2014 (Bassily et al., , 2019;; Feldman et al., 2020; Asi et al., 2021a Asi et al., ,b, 2022b)) .Online learning with non-stochastic adversaries. Online learning with non-stochastic adversaries has been extensively studied (Cesa-Bianchi and Lugosi, 2006; Littlestone and Warmuth, 1994; Freund and Schapire, 1997; Zinkevich, 2003) . Federated online learning with non-stochastic adversaries, a more recent development, was introduced by Hong and Chae (2021). Differentially private online learning with non-stochastic adversaries was pioneered by Dwork et al. (2010) . Several studies have explored OPE problem with DP constraints (Jain et al., 2012; Guha Thakurta and Smith, 2013; Jain and Thakurta, 2014; Agarwal and Singh, 2017; Asi et al., 2022b) . Specifically, Jain and Thakurta (2014) and Agarwal and Singh (2017) focused on methods based on follow the regularized leader. Asi et al. (2022b) proposed an algorithm using the shrinking dartboard method.Studies addressing differentially private online learning with non-stochastic adversaries in other contexts have also made significant strides. Kaplan et al. (2023b) focused on online classification problem with joint DP constraints. Fichtenberger et al. (2023) introduced a constant improvement. Gonen et al. (2019) and Kaplan et al. (2023a) studied the relationship between private learning and online learning. Agarwal et al. (2023a) and Agarwal et al. (2023b) studied the DP online convex optimization problem. Research on differentially private federated online learning with non-stochastic adversaries is very limited to the best of our knowledge.Online learning under realizability assumption. Several works have studied online learning in the realizable setting. Srebro et al. (2010) studied mirror descent for online optimization. Shalev-Shwartz et al. (2012) studied the weighted majority algorithm. There is also a line of work studying stochastic convex optimization in the realizable setting (Cotter et al., 2011; Ma et al., 2018; Vaswani et al., 2019; Liu and Belkin, 2018; Woodworth and Srebro, 2021; Asi et al., 2022a) . Additionally, some researchers have recently focused on the variance or the path length of the best expert (Cesa-Bianchi et al., 2007; Steinhardt and Liang, 2014; Wei and Luo, 2018; Bubeck et al., 2019) . When DP constraint is considered, Asi et al. (2023) introduced algorithms using the sparse vector technique. Golowich and Livni (2021) studied DP online classification.Multi-armed bandits with DP. Research on DP multi-armed bandits has developed along various lines (Mishra and Thakurta, 2015; Tossou and Dimitrakakis, 2016; Sajed and Sheffet, 2019; Azize and Basu, 2022) . Further, Hu and Hegde (2022) proposed a Thompson-sampling-based approach, Tao et al. (2022) explored the heavy-tailed rewards scenario, and Chowdhury and Zhou (2022a) achieved optimal regret in a distributed setting. Additionally, Ren et al. (2020) and Zheng et al. (2020) investigated local DP constraints. For linear contextual bandits with DP, significant studies were conducted by Shariff and Sheffet (2018) ; Wang et al. (2020 Wang et al. ( , 2022b) ) and Hanna et al. (2022) .Differentially private federated online prediction has many important real-world applications. We provide three examples below.Personalized Healthcare: Consider a federated online prediction setting where patients' wearable devices collect and process health data locally, and the central server aggregates privacy-preserving updates from devices to provide health recommendations or alerts. DP federated online prediction can speed up the learning process and improve prediction accuracy without exposing individual users' health data, thus ensuring patient privacy.Financial Fraud Detection: DP federated online prediction can also enhance fraud detection systems across banking and financial services. Each client device (e.g. PC) locally analyzes transaction patterns and flags potential fraud without revealing sensitive transaction details to the central server. The server's role is to collect privacy-preserving updates from these clients to improve the global fraud detection model. This method ensures that the financial company can dynamically adapt to new fraudulent tactics, improving detection rates while safeguarding customers' financial privacy.Personalized Recommender Systems: Each client (e.g. smartphone) can personalize content recommendations by analyzing user interactions and preferences locally. The central server (e.g. company) aggregates privacy-preserving updates from all clients to refine the recommendation model. Thus, DP federated online prediction improves the whole recommender system performance while maintaining each client's privacy.In Fed-DP-OPE-Stoch, we run a DP-FW subroutine (Asi et al., 2021b) at each client i in each phase p. DP-FW maintains T 1 binary trees indexed by 1 ≤ j ≤ T 1 , each with depth j, where T 1 is a predetermined parameter. An example of the tree structure is shown below. We introduce the notation s ∈ {0, 1} ≤j to denote vertices within binary tree j. ∅ signifies the tree's root. For any s, s ′ ∈ {0, 1} ≤j , if s = s ′ 0, then s denotes the left child of s ′ . Conversely, when s = s ′ 1, s is attributed as the right child of s ′ . For each client i, each vertex s in the binary tree j corresponds to a parameter x i,j,s and a gradient estimate v i,j,s . Each client iteratively updates parameters and gradient estimates by visiting the vertices of a binary tree according to the Depth-First Search (DFS) order: as it visits a left child vertex s, the algorithm maintains the parameter x i,j,s and the gradient estimate v i,j,s identical to those of its parent vertex s ′ , i.e. v i,j,s = v i,j,s ′ and x i,j,s = x i,j,s ′ . As it proceeds to a right child vertex, we uniformly select 2 -|s| b loss functions from set B i,p = {l i,2 p-2 , . . . , l i,2 p-1 -1 } to subset B i,j,s without replacement, where b denoting the predetermined batch size and |s| representing the depth of the vertex s. Then the algorithm improves the gradient estimate v i,j,s at the current vertex s of tree j using the estimate v i,j,s ′ at the parent vertex s ′ , i.e. v i,j,s = v i,j,s ′ + ∇l(x i,j,s ; B i,j,s ) -∇l(x i,j,s ′ ; B i,j,s ).(3)Algorithm 3 DP-FW at client i (Asi et al., 2021b) 1: Input: Sample set B, number of trees T 1 , batch size b.2: for j = 1 to T 1 do 3:Set x i,j,∅ = x i,j-1,Lj-1Uniformly select b samples to B i,j,∅v i,j,∅ = ∇l i,t (x i,j,∅ ; B i,j,∅ ) 6:for s ∈ DFS[j] do 7:Let s = s ′ a where a ∈ {0, 1}8:if a == 0 then 9:v i,j,s = v i,j,s ′ ; x i,j,s = x i,j,s ′ 10:else 11:Uniformly select 2 -|s| b samples to B i,j,s 12:Update v i,j,s according to Equation (3)13:end if 14:end for 15: end for 16: Return {v i,j,s } j∈[T1],s∈{0,1} ≤j where ∇l(•; B i,j,s ) = 1 |Bi,j,s| l∈Bi,j,s ∇l(•), and B i,j,s is the subset of loss functions at vertex s in the binary tree j for client i. The full algorithm is shown in Algorithm 3. O (α + β) log T T log d m + √ αβ log d √ T log T m 1 4 √ ε with (iii) a communication cost of O m 5 4 d T εβ α log d .We define population loss asL t (x) = E[ 1 m m i=1 l i,t (x i,t )].The per-client regret can be expressed asE T t=1 L t (x i,t ) -min x ⋆ ∈X T t=1 L t (x ⋆ ). We use v i,p,k , w i,p,k , x i,p,k and η i,p,k to denote quantities corresponding to phase p, iteration k, and client i. Also we introduce some average quantitiesvp,k = 1 m m i=1 v i,p,k and wp,k = 1 m m i=1 w i,p,k .To prove the theorem, we start with Lemma 1 that gives pure privacy guarantees.Lemma 1. Assume that 2 T1 ≤ b. Setting λ i,j,s = 4α2 j bε , Fed-DP-OPE-Stoch is ε-DP.Proof. Let S and S ′ be two neighboring datasets and assume that they differ in sample l i1,t1 or l ′ i1,t1 , where 2 p1-1 ≤ t 1 < 2 p1 . Let B i1,j,s be the set that contains l i1,t1 or l ′ i1,t1 . Recall that |B i1,j,s | = 2 -|s| b. The key point is that this set is used in the calculation of v i1,p1,k for at most 2 j-|s| iterates, i.e. the leaves that are descendants of the vertex. Let k 0 and k 1 be the first and last iterate such that B i1,j,s is used for the calculation of v i1,p1,k , hence k 1 -k 0 + 1 ≤ 2 j-|s| . First, we show that (⟨c n , v 1,1,1 ⟩, . . . , ⟨c n , v m,P,K ⟩) ≈ (ε,0) (⟨c n , v ′ 1,1,1 ⟩, . . . , ⟨c n , v ′ m,P,K ⟩) holds for 1 ≤ n ≤ d. For our purpose, it suffices to establish that (⟨c n , v i1,p1,k0 ⟩, . . . , ⟨c n , v i1,p1,k1 ⟩) ≈ (ε,0) (⟨c n , v ′ i1,p1,k0 ⟩, . . . , ⟨c n , v ′ i1,p1,k1 ⟩) holds for 1 ≤ n ≤ d, since l i1,t1 or l ′ i1,t1 is only used in client i 1 , at phase p 1 and iteration k 0 , . . . , k 1 . Therefore it is enough to show that ⟨c n , v i1,p1,k ⟩ ≈ ( ε2 j-|s| ,0) ⟨c n , v ′ i1,p1,k ⟩ holds for k 0 ≤ k ≤ k 1 and 1 ≤ n ≤ d, because k 1 -k 0 + 1 ≤ 2 j-|s| . Note that |⟨c n , v i1,p1,k -v ′ i1,p1,k ⟩| ≤ 4α 2 -|s| b .Setting λ i,j,s = 4α2 j bε and applying standard results of Laplace mechanism (Dwork et al. (2014) ) lead to our intended results. Finally, we can show that (x 1,1,K , . . . , x m,P,K ) ≈ (ε,0) (x ′ 1,1,K , . . . , x ′ m,P,K ) by post-processing.To help prove the upper bound of the regret, we introduce some lemmas first. Lemma 2. Let t be the time-step, p be the index of phases, i be the index of the clients, and (j, s) be a vertex. For every index 1 ≤ k ≤ d of the vectors, we haveE [exp {c(v p,j,s,k -∇L t,k (x i,p,j,s ))}] ≤ exp O(1)c 2 (α 2 + β 2 ) bm ,where vp,j,s = 1 m m i=1 v i,p,j,s .Proof. Let us fix p, t, k and i for simplicity and let A j,s = vp,j,s,k -∇L t,k (x i,p,j,s ). We prove the lemma by induction on the depth of the vertex, i.e., |s|. If |s| = 0, then v i,p,j,∅ = ∇l(x i,p,j,∅ ; B i,p,j,∅ ) where B i,p,j,∅ is a sample set of size b. Therefore we haveE[exp cA j,s ] = E[exp c(v p,j,∅,k -∇L t,k (x i,p,j,∅ )] = E   exp c   1 mb m i=1 s∈B i,p,j,∅ ∇l k (x i,p,j,∅ ; s) -∇L t,k (x i,p,j,∅ )     = s∈B i,p,j,∅ i∈[m] E exp c bm (∇l k (x i,p,j,∅ ; s) -∇L t,k (x i,p,j,∅ )) ≤ exp c 2 α 2 2bm ,where the last inequality holds because for a random variable X ∈ [-α, α], we haveE[exp c(X -E[X])] ≤ exp c 2 α 2 2 .Assume the depth of the vertex |s| ≥ 0 and let s = s ′ a where a ∈ {0, 1}. If a = 0, clearly the lemma holds. If a = 1, recall that v i,p,j,s = v i,p,j,s ′ + ∇l(x i,p,j,s ; B i,p,j,s ) -∇l(x i,p,j,s ′ ; B i,p,j,s ), thenA j,s = vp,j,s,k -∇L t,k (x i,p,j,s ) = A j,s ′ + 1 m m i=1 ∇l k (x i,p,j,s ; B i,p,j,s ) - 1 m m i=1 ∇l k (x i,p,j,s ′ ; B i,p,j,s ) -∇L t,k (x i,p,j,s ) + ∇L t,k (x i,p,j,s ′ )Let B i,p,<(j,s) = ∪ (j1,s1)<(j,s) B i,p,j1,s1 be the set containing all the samples used up to vertex (j, s) in phase p at client i. We haveE [exp cA j,s ] = E exp c(A j,s ′ + 1 m m i=1 ∇l k (x i,p,j,s ; B i,p,j,s ) - 1 m m i=1 ∇l k (x i,p,j,s ′ ; B i,p,j,s ) × exp -∇L t,k (x i,p,j,s ) + ∇L t,k (x i,p,j,s ′ ) = E E exp c(A j,s ′ + 1 m m i=1 ∇l k (x i,p,j,s ; B i,p,j,s ) - 1 m m i=1 ∇l k (x i,p,j,s ′ ; B i,p,j,s ) -∇L t,k (x i,p,j,s ) + ∇L t,k (x i,p,j,s ′ ) B i,p,<(j,s) = E E exp (cA j,s ′ ) B i,p,<(j,s) × E[exp c( 1 m m i=1 ∇l k (x i,p,j,s ; B i,p,j,s ) - 1 m m i=1∇l k (x i,p,j,s ′ ; B i,p,j,s )-∇L t,k (x i,p,j,s ) + ∇L t,k (x i,p,j,s ′ ) B i,p,<(j,s) .Since l i,t (•; s) is β-smooth w.r.t. ∥ • ∥ 1 , we have|∇l k (x i,p,j,s ; B i,p,j,s ) -∇l k (x i,p,j,s ′ ; B i,p,j,s )| ≤ β∥x i,p,j,s -x i,p,j,s ′ ∥ 1 .Since vertex (j, s) is the right son of vertex (j, s ′ ), the number of updates between x i,p,j,s and x i,p,j,s ′ is at most the number of leafs visited between these two vertices i.e. 2 j-|s| . Therefore we have∥x i,p,j,s -x i,p,j,s ′ ∥ 1 ≤ η i,p,j,s ′ 2 j-|s| ≤ 2 2-|s| .By using similar arguments to the case |s| = 0, we can getE exp c( 1 m m i=1 ∇l k (x i,p,j,s ; B i,p,j,s ) - 1 m m i=1 ∇l k (x i,p,j,s ′ ; B i,p,j,s ) × exp -∇L t,k (x i,p,j,s ) + ∇L t,k (x i,p,j,s ′ ) B i,p,<(j,s) ≤ exp O(1)c 2 β 2 2 -2|s| m|B i,p,j,s | ≤ exp O(1)c 2 β 2 2 -|s| bm .Then we getE[exp cA j,s ] ≤ E[exp cA j,s ′ ] exp O(1)c 2 β 2 2 -|s| bm .Applying this inductively, we have for every index1 ≤ k ≤ d E[exp cA j,s ] ≤ exp O(1)c 2 (α 2 + β 2 ) bm .Lemma 3 upper bounds the variance of the average gradient. Lemma 3. At phase p, for each vertex (j, s) and 2 p-1 ≤ t < 2 p -1, we haveE [∥v p,j,s -∇L t (x i,p,j,s )∥ ∞ ] ≤ (α + β)O log d bm ,where vp,j,s = 1 m m i=1 v i,p,j,s .Proof. Lemma 2 implies that vp,j,s,k -∇L t,k (x i,p,j,s ) is O( α 2 +β 2 bm )-sub-Gaussian for every index 1 ≤ k ≤ d of the vectors. Applying standard results of the maximum of d sub-Gaussian random variables, we getE[∥v p,j,s -∇L t (x i,p,j,s )∥ ∞ ] ≤ O α 2 + β 2 bm log d.Lemma 4 gives the tail bound of the sum of i.i.d. random variables following Laplace distribution. Lemma 4. Let ξ i,n be IID random variables following the distribution Lap(λ i,j,s ). Then we haveE max n:1≤n≤d m i=1 ξ i,n ≤ O( √ mλ i,j,s ln d).Proof. ξ i,n 's are md IID random variables following the distribution Lap(λ i,j,s ). We note that j, s .E [exp(uξ i,n )] = 1 1 -λ i,j,s 2 u 2 , |u| ≤ 1 λ i,Since 1 1-λi,j,s 2 u 2 ≤ 1 + 2λ i,j,s 2 u 2 ≤ exp(2λ i,j,s 2 u 2 ), when |u| ≤ 1 2λi,j,s , ξ i,n is sub-exponential with parameter (4λ i,j,s 2 , 2λ i,j,s ). Applying standard results of linear combination of sub-exponential random variables, we can conclude that m i=1 ξ i,n , denoted as Y n , is sub-exponential with parameter (4mλ i,j,s 2 , 2λ i,j,s ). From standard results of tail bounds of sub-exponential random variables, we haveP (|Y n | ≥ c) ≤ 2 exp - c 2 8mλ i,j,s 2 , if 0 ≤ c ≤ 2mλ i,j,s , P(|Y n | ≥ c) ≤ 2 exp - c 4λ i,j,s , if c ≥ 2mλ i,j,s . Since P max n:1≤n≤d |Y n | ≥ c ≤ n:1≤n≤d P (|Y n | ≥ c), we have P( max n:1≤n≤d |Y n | ≥ c) ≤ 2d exp - c 2 8mλ i,j,s 2 , if 0 ≤ c ≤ 2mλ i,j,s , P( max n:1≤n≤d |Y n | ≥ c) ≤ 2d exp - c 4λ i,j,s , if c ≥ 2mλ i,j,s .Then we haveE max n:1≤n≤d |Y n | = ∞ 0 P max n:1≤n≤d |Y n | ≥ c dc = √ 8m ln dλ i,j,s + 2mλi,j,s √ 8m ln dλi,j,s P max n:1≤n≤d |Y n | ≥ c dc + ∞ 2mλi,j,s P max n:1≤n≤d |Y n | ≥ c dc ≤ √ 8m ln dλ i,j,s + 2mλi,j,s √ 8m ln dλi,j,s 2 exp ln d - c 2 8mλ i,j,s 2 dc + ∞ 2mλi,j,s 2 exp ln d - c 4λ i,j,s dc ≤ √ 8m ln dλ i,j,s + √ 8mλ i,j,s +∞ -∞ exp -u 2 du + 8λ i,j,s ∞ 2/m-ln d exp(-u)du ≤ √ 8m ln dλ i,j,s + √ 8mλ i,j,s +∞ -∞ exp -u 2 du + 8λ i,j,s ln d + 8λ i,j,s ∞ 0 exp(-u)du = √ 8m ln dλ i,j,s + √ 8mπλ i,j,s + 8λ i,j,s ln d + 8λ i,j,s = O( √ mλ i,j,s ln d).Lemma 5. Setting λ i,j,s = 4α2 j bε , we haveE[⟨v p,k , wp,k ⟩] ≤ E min w∈X ⟨v p,k , w⟩ + O α2 j ln d bε √ m .Proof. Since wp,k = arg min cn:1≤n≤d1 m m i=1 ⟨c n , v i,p,k ⟩ + ξ i,n, where ξ i,n ∼ Lap(λ i,j,s ), we denote wp,k as c n ⋆ and we have⟨ wp,k , vp,k ⟩ = ⟨c n ⋆ , vp,k ⟩ = min n:1≤n≤d ⟨c n , vp,k ⟩ + 1 m m i=1 ξ i,n - 1 m m i=1 ξ i,n ⋆ ≤ min n:1≤n≤d ⟨c n , vp,k ⟩ + 1 m max n:1≤n≤d m i=1 ξ i,n - 1 m min n:1≤n≤d m i=1 ξ i,n ≤ min n:1≤n≤d ⟨c n , vp,k ⟩ + 2 m max n:1≤n≤d m i=1 ξ i,n .Applying Lemma 4, we getE[⟨v p,k , wp,k ⟩] ≤ E min w∈X ⟨v p,k , w⟩ + O λ i,j,s ln d √ m .With the lemmas above, we are ready to prove Theorem 1.Proof. Lemma 1 implies the claim about privacy. We proceed to prove the regret upper bound.L t (x i,p,k+1 ) (a) ≤ L t (x i,p,k ) + ⟨∇L t (x i,p,k ), x i,p,k+1 -x i,p,k ⟩ + β ∥x i,p,k+1 -x i,p,k ∥ 2 1 2 (b) ≤ L t (x i,p,k ) + η i,p,k ⟨∇L t (x i,p,k ), wp,k -x i,p,k ⟩ + 1 2 βη i,p,k 2 = L t (x i,p,k ) + η i,p,k ⟨∇L t (x i,p,k ), x ⋆ -x i,p,k ⟩ + η i,p,k ⟨∇L t (x i,p,k ) -vp,k , wp,k -x ⋆ ⟩ + η i,p,k ⟨v p,k , wp,k -x ⋆ ⟩ + 1 2 βη i,p,k 2 (c) ≤ L t (x i,p,k ) + η i,p,k [L t (x ⋆ ) -L t (x i,p,k )] + η i,p,k ∥∇L t (x i,p,k ) -vp,k ∥ ∞ + η i,p,k (⟨v p,k , wp,k ⟩ -min w∈X ⟨v p,k , w⟩) + 1 2 βη i,p,k 2 ,where (a) is due to β-smoothness, (b) is because of the updating rule of x i,p,k , and (c) follows from the convexity of the loss function and Hölder's inequality.Subtracting L t (x ⋆ ) from each side and taking expectations, we haveE[L t (x i,p,k+1 ) -L t (x ⋆ )] ≤ (1 -η i,p,k )E[L t (x i,p,k ) -L t (x ⋆ )] + η i,p,k E[∥∇L t (x i,p,k ) -vp,k ∥ ∞ ] + η i,p,k E[⟨v p,k , wp,k ⟩ -min w∈X ⟨v p,k , w⟩] + 1 2 βη i,p,k 2 .Applying Lemma 5 and Lemma 3, we haveE[L t (x i,p,k+1 ) -L t (x ⋆ )] ≤ (1 -η i,p,k )E[L t (x i,p,k ) -L t (x ⋆ )] + η i,p,k (α + β)O log d bm + η i,p,k α2 j bε O ln d √ m + 1 2 βη i,p,k 2 . Let α k = η i,p,k (α + β)O log d bm + η i,p,k α2 j bε O ln d √ + 1 2 βη i,p,k 2 .We simplify the notion of η i,p,k to η k . Then we haveE[L t (x i,p,k ) -L t (x ⋆ )] ≤ K k ′ =1 α k K-1 i>k (1 -η k ′ ) = K k=1 α k (k + 1)k K(K -1) ≤ K k=1 α k (k + 1) 2 (K -1) 2 ,where η k = 2 k+1 . Since K = 2 T1 , simply algebra implies thatE[L t (x i,p,K ) -L t (x ⋆ )] ≤ O (α + β) log d bm + α2 T1 ln d bε √ m + β 2 T1 . (4) At iteration 2 p-1 ≤ t < 2 p , setting b = 2 p-1 (p-1) 2 and T 1 = 1 2 log bεβ √ m α log din Equation ( 4), we haveE[L t (x i,p,K ) -L t (x ⋆ )] ≤ O (α + β)p log d 2 p m + p √ αβ log d m 1 4 √ 2 p ε .Therefore, the total regret from time step 2 p to 2 p+1 -1 is at mostE   2 p+1 -1 t=2 p L t (x i,t ) -min u∈X 2 p+1 -1 t=2 p L t (u)   ≤ O (α + β)p 2 p log d m + p √ αβ log d √ 2 p m 1 4 √ ε .Summing over p, we can get Proof. Similar to the proof of Theorem 1, we can show thatE T t=1 L t (x i,t ) -min u∈X T t=1 L t (u) ≤ log T p=1 O (α + β)p 2 p log d m + p √ αβ log d √ 2 p m 1 4 √ ε ≤ O (α + β) log T p=1 p 2 p log d m + √ αβ log d m 1 4 √ ε log T p=1 p √ 2 p ≤ O (α + β) log T T log d m + √ αβ log d √ T log T m 1 4 √ ε .E[L t (x i,p,K ) -L t (x ⋆ )] ≤ O (α + β) log d bm + α2 T1 ln d bε √ m + β 2 .(5)At iteration 2 p-1 ≤ t < 2 p , setting b = 2 p-1 and T 1 = 1 in Equation ( 5), we haveE[L t (x i,p,K ) -L t (x ⋆ )] ≤ O (α + β) log d 2 p m + α ln d 2 p ε √ m + β . Since β = O( log d √ mT ε ), we have E[L t (x i,p,K ) -L t (x ⋆ )] ≤ O (α + β) log d 2 p m + α ln d 2 p ε √ m .Therefore, the total regret from time step 2 p to 2 p+1 is at mostE   2 p+1 -1 t=2 p L t (x i,t ) -min u∈X 2 p+1 -1 t=2 p L t (u)   ≤ O 2 p log d m + log d √ mε .Summing over p, we can getE T t=1 L t (x i,t -min u∈X T t=1 L t (u) ≤ log T p=1 O 2 p log d m + α log d √ mε ≤ O log T p=1 2 p log d m + log d log T √ mε ≤ O T log d m + log d log T √ mε .The proof of the DP guarantee and communication costs follows from the proof of Theorem 1.C.3 Theorem 6 (for approximate DP) Theorem 6. Let δ ≤ 1/T . Assume that loss functionl i,t (•) is convex, α-Lipschitz, β-smooth w.r.t. ∥ • ∥ 1 . Assume ε ≤ (α log(2 p-1 /δ) log d) 1/4 √ p-1 (β2 p-1 ) 1/4 . Setting λ i,j,s = α2 T 1 /2 log(2 p-1 /δ) bε , b = 2 p-1(p-1) 2 , and T 1 = 2 3 log bε √ mβ α log(2 p-1 /δ) log d , Fed-DP-OPE-Stoch is (ε, δ)-O (α + β) log T T log d m + α 2/3 β 1/3 log 2/3 (d) log 2/3 (1/δ)T 1/3 log 4/3 (T ) m 1/3 ε 2/3 .Proof. We apply the following lemma to prove privacy in this setting.Lemma 6 (Asi et al. (2021b) , Lemma 4.4). Let b ≥ 2 T1 , δ ≤ 1/T and ε ≤ 2 -T1 log(1/δ). Settingλ i,j,s = α2 T 1 /2 log(2 p-1 /δ) bε , we have Fed-DP-OPE is (O(ε), O(δ))-DP.Theorem 6 then follows using similar arguments to the proof of Theorem 1.In this section, we extend our Fed-DP-OPE-Stoch algorithm to the setting where client-server communication is secure with some modifications, achieving better utility performance.We present the algorithm design in Algorithm 4 and Algorithm 5. We change the local privatization process to a privatization process on the server side. Specifically, in Line 8, when communication is triggered, each client sends {⟨c n , v i,j,s ⟩} n∈ [d] to the server, where c 1 , . . . , c d represents d vertices of decision set X = ∆ d . In Line 5, after receiving {⟨c n , v i,j,s ⟩} n∈ [d] from all clients, the central server privately predicts a new expert:EQUATIONwhere ζ n ∼ Lap(µ j,s ) and µ j,s = 4α2 j bmε . Other components remain the same. Set B i,p = {l i,2 p-2 , . . . , l i,2 p-1 -1 } 5:Set k = 1 and x i,p,1 = x i,p-1,K 6:{v i,j,s } j∈[T1],s∈{0,1} ≤j = DP-FW (B i,p , T 1 , b) 7:for all leaf vertices s reached in DP-FW do 8:Communicate to server: {⟨c n , v i,j,s ⟩} n∈ [d] 9:Receive from server: wj,s 10:Update x i,p,k according to Equation ( 2)11: Update k = k + 1 12:end for 13:Final iterate outputs x i,p,K 14:for t = 2 p-1 to 2 p -1 do 15:Receive loss l i,t : X → R and pay cost l i,t (x i,p,K ) Receive from clients: {⟨c n , v i,j,s ⟩} n∈ [d] 5: wj,s = arg min cn:1≤n≤d1 m m i=1 ⟨c n , v i,j,s ⟩ + ζ n 6:Communicate to clients: wj,s 7: end for Now we present the theoretical guarantees in this setting. Theorem 7. Assume that loss function li,t (•) is convex, α-Lipschitz, β-smooth w.r.t. ∥ • ∥ 1 . Fed-DP- OPE-Stoch (i) satisfies ε-DP and (ii) achieves the per-client regret of O (α + β) log T T log d m + √ αβ log d √ T log T √ m √ ε , with (iii) a communication cost of O m 3 2 d T εβ α log d .To prove the theorem, we start with Lemma 7 that gives pure privacy guarantees.Lemma 7. Assume that 2 T1 ≤ b. Setting µ j,s = 4α2 j bmε , Fed-DP-OPE-Stoch is ε-DP.Proof. Let S and S ′ be two neighboring datasets and assume that they differ in sample l i1,t1 or l ′ i1,t1 , where 2 p1-1 ≤ t 1 < 2 p1 . The algorithm is ε-DP if we have (x 1,1,K , . . . , x m,P,K ) ≈ (ε,0) (x 1,1,K , . . . , x ′ m,P,K ).Let B i1,j,s be the set that contains l i1,t1 or l ′ i1,t1 . Recall that |B i1,j,s | = 2 -|s| b. The key point is that this set is used in the calculation of v i1,p1,k for at most 2 j-|s| iterates, i.e. the leaves that are descendants of the vertex. Let k 0 and k 1 be the first and last iterate such that B i1,j,s is used for the calculation of v i1,p1,k , hence k 1 -k 0 + 1 ≤ 2 j-|s| . For a sequence a i , . . . , a j , we use the shorthand a i:j = {a i , . . . , a j }.Step 1: x 1:m,p1,k0:k1 ≈ (ε,0) x ′ 1:m,p1,k0:k1 and wp1,k0:k1 ≈ (ε,0) w′ p1,k0:k1 by basic composition, post-processing and report noisy maxWe will show that (x 1,p1,k0 , . . . , x m,p1,k1 ) and(x ′ 1,p1,k0 , . . . , x ′ m,p1,k1 ) are ε-indistinguishable. Since B i1,j,s is used to calculate v i1,p1,k for at most 2 j-|s| iterates, i.e. k 1 -k 0 + 1 ≤ 2 j-|s| , it is enough to show that wp1,k ≈ ( ε 2 j-|s| ,0) w′ p1,k for k 0 ≤ k ≤ k 1and then apply basic composition and postprocessing. Note that for everyk 0 ≤ k ≤ k 1 , the sensitivity |⟨c n , v i1,p1,k -v ′ i1,p1,k ⟩| ≤ 4α 2 -|s| b , therefore, | 1 m m i=1 ⟨c n , v i,p1,k ⟩ -1 m m i=1 ⟨c n , v ′ i,p1,k ⟩| ≤ 4α 2 -|s| mb .Using privacy guarantees of report noisy max (Lemma 15), we have wp1,k ≈ ( ε2 j-|s| ,0) w′ p1,k for k 0 ≤ k ≤ k 1 with µ j,s = 4α2 j bmε .Step 2: x 1:m,1:P,K ≈ (ε,0) x ′ 1:m,1:P,K by post-processing In order to show (x 1,1,K , . . . , x m,P,K ) ≈ (ε,0) (x ′ 1,1,K , . . . , x ′ m,P,K ), we only need to prove that(x 1,p1,K , . . . , x m,p1,K ) ≈ (ε,0) (x ′ 1,p1,K , . . . , x ′ m,p1,K) and apply post-processing. It is enough to show that iterates (x 1,p1,1 , . . . , x m,p1,K ) and (x ′ 1,p1,1 , . . . , x ′ m,p1,K ) is ε-indistinguishable. The iterates x 1:m,p1,1:k0-1 and x ′ 1:m,p1,1:k0-1 do not depend on l i1,t1 or l ′ i1,t1 , hence 0indistinguishable. Moreover, given that (x 1,p1,k0 , . . . , x m,p1,k1 ) and (x ′ 1,p1,k0 , . . . , x ′ m,p1,k1 ) are ε-indistinguishable, it is clear that (x 1,p1,k1+1 , . . . , x m,p1,K ) and (x ′ 1,p1,k1+1 , . . . , x ′ m,p1,K ) are εindistinguishable by post-processing.To help prove the upper bound of the regret, we introduce some lemmas first.Lemma 8. Setting µ j,s = 4α2 j mbε , we haveE[⟨v p,k , wp,k ⟩] ≤ E min w∈X ⟨v p,k , w⟩ + O α2 j ln d mbε .Proof. Since wp,k = arg min cn:1≤n≤d1 m m i=1 ⟨c n , v i,p,k ⟩ + ζ n , where ζ n ∼ Lap(µ j,s), we denote wp,k as c n ⋆ and we have⟨ wp,k , vp,k ⟩ = ⟨c n ⋆ , vp,k ⟩ = min n:1≤n≤d (⟨c n , vp,k ⟩ + ζ n ) -ζ n ⋆ ≤ min n:1≤n≤d ⟨c n , vp,k ⟩ + 2 max n:1≤n≤d |ζ n |.Standard results for the expectation of maximum of d i.i.d. Laplace random variables imply thatE max n:1≤n≤d |ζ n | ≤ O(µ j,s ln d). Therefore, E[⟨v p,k , wp,k ⟩] ≤ E min w∈X ⟨v p,k , w⟩ + O (µ j,s ln d) .Then we are ready to prove Theorem 7.Proof. Lemma 7 implies the claim about privacy. Following the same arguments in the proof of Theorem 1, we can getE[L t (x i,p,k+1 ) -L t (x ⋆ )] ≤ (1 -η i,p,k )E[L t (x i,p,k ) -L t (x ⋆ )] η i,p,k E[∥∇L t (x i,p,k ) -vp,k ∥ ∞ ] + η i,p,k E[⟨v p,k , wp,k ⟩ -min w∈X ⟨v p,k , w⟩] + 1 2 βη i,p,k 2 .Applying Lemma 8 and Lemma 3, we haveE[L t (x i,p,k+1 ) -L t (x ⋆ )] ≤ (1 -η i,p,k )E[L t (x i,p,k ) -L t (x ⋆ )] + η i,p,k (α + β)O log d bm + η i,p,k α2 j bε O ln d m + 1 2 βη i,p,k 2 . Let α k = η i,p,k (α + β)O log d bm + η i,p,k α2 j bε O ln d m + 1 2 βη i,p,k 2 .We simplify the notion ofη i,p,k to η k . Then we have E[L t (x i,p,k ) -L t (x ⋆ )] ≤ K k ′ =1 α k K-1 i>k (1 -η k ′ ) = K k=1 α k (k + 1)k K(K -1) ≤ K k=1 α k (k + 1) 2 (K -1) 2 ,whereEQUATIONAt iteration 2 p-1 ≤ t < 2 p , setting b = 2 p-1 (p-1) 2 and T 1 = 1 2 log bεβm α log d , we haveE[L t (x i,p,K ) -L t (x ⋆ )] ≤ O (α + β)p log d 2 p m + p √ αβ log d √ m √ 2 p ε .Summing over all the timesteps, we haveE T t=1 L t (x i,t ) -min u∈X T t=1 L t (u) ≤ O (α + β) log T T log d m + √ αβ log d √ T log T √ mε .The proof of communication cost is similar to that in proof of Theorem 1.Theorem 8 (Restatement of Theorem 2). For any federated OPE algorithm against oblivious adversaries, the per-client regret is lower bounded by Ω( √ T log d). Let ε ∈ (0, 1] and δ = o(1/T ), for any (ε, δ)-DP federated OPE algorithm, the per-client regret is lower bounded by Ω min log d ε , T .Proof. Consider the case when all clients receive the same loss function from the oblivious adversary at each time step, i.e. l i,t = l ′ t . Then we define the average policy among all clientsp ′ t (k) = 1 m m i=1 p i,t (k), ∀k ∈ [d]. Now the regret is E 1 m m i=1 T t=1 l i,t (x i,t ) - 1 m m i=1 T t=1 l i,t (x ⋆ ) = E 1 m m i=1 T t=1 l ′ t (x i,t ) - T t=1 l ′ t (x ⋆ ) = 1 m m i=1 T t=1 d k=1 p i,t (k) • l ′ t (k) - T t=1 l ′ t (x ⋆ ) = T t=1 d k=1 1 m m i=1 p i,t (k) • l ′ t (k) - T t=1 l ′ t (x ⋆ ) = T t=1 d k=1 p t (k) • l ′ t (k) - T t=1 l ′ t (x ⋆ ).Note that p ′ t (k) is defined by p 1,t (k), . . . , p m,t (k), which in turn are determined by l 1,1 , . . . , l m,t-1 . According to our choice ofl i,t = l ′ t , p ′ t (k) is determined by l ′ 1 , l ′ 2 , . . . , l ′ t-1 . Therefore p ′ 1 , p ′ 2 , . . . , p ′ tare generated by a legitimate algorithm for online learning with expert advice problems.There exists a sequence of losses l ′ 1 , l ′ 2 , . . . , l ′ t such that for any algorithm for online learning with expert advice problem, the expected regret satisfies (Cesa-Bianchi and Lugosi ( 2006), Theorem 3.7)T t=1 d k=1 p ′ t (k) • l ′ t (k) - T t=1 l ′ t (x ⋆ ) ≥ Ω( T log d).Therefore, we haveE 1 m m i=1 T t=1 l i,t (x i,t ) - 1 m m i=1 T t=1 l i,t (x ⋆ ) ≥ Ω( T log d).From Lemma 9, if ε ∈ (0, 1] and δ = o(1/T ), then there exists a sequence of losses l ′ 1 , l ′ 2 , . . . , l ′ t such that for any (ε, δ)-DP algorithm for online learning with expert advice problem against oblivious adversaries, the expected regret satisfiesT t=1 d k=1 p ′ t (k) • l ′ t (k) - T t=1 l ′ t (x ⋆ ) ≥ Ω min log d ε , T .Therefore, we have for any (ε, δ)-DP algorithm,E 1 m m i=1 T t=1 l i,t (x i,t ) - 1 m m i=1 T t=1 l i,t (x ⋆ ) ≥ Ω min log d ε , T .Lemma 9. Let ε ∈ (0, 1] and δ = o(1/T ). There exists a sequence of losses l 1 , . . . , l T such that for any (ε, δ)-DP algorithm A for DP-OPE against oblivious adversaries satisfies Proof. DP guarantee: Fix neighboring datasets y and y ′ that are inputs to algorithm M. According to the algorithm design for 1-Select d , we stream y and y ′ to a DP-OPE algorithm A. Since A is (ε, δ)-DP, and M only post-processes the outputs received from A, therefore M is (ε, δ)-DP.T t=1 l t (x t ) -min x ⋆ ∈[d]Regret upper bound: Fix a dataset y. Note that if α ≥ n, the accuracy guarantee for M is vacuous. Now assume α < n. Let γ be the regret of M, that is,γ = Reg 1-Select d (M) = 1 n n i=1 y i (b) -min x ⋆ ∈[d] n i=1 y i (x ⋆ ) ,where b is the output of M.The main observation in the regret analysis is that if α is small, so is γ. Specifically, the regret of M is at most α n . Therefore, γ ≤ α n .Lemma 11 (Jain et al. (2023) Proof. I introduce two prototype loss functions first: let l 0 (x) = 0 for all x ∈ [d] and for j ∈ [d] let l j (x) be the function that has l j (x) = 0 for x = j and otherwise l j (x) = 1. Then we define d loss sequences S j = (l j 1,1 , . . . , l j m,T ), such thatl j i,t = l 0 if t = 1, . . . , T -k, l j else;where k = log d 2mε and j ∈ [d]. The oblivious adversary picks one of the d sequences S 1 , . . . , S d uniformly at random. Assume towards a contradiction that Em i=1 T t=1 l i,t (x i,t ) - m i=1 T t=1 l i,t (x ⋆ ) ≤ log(d)32ε . This implies that there exists d/2 sequences such that the expected regret satisfiesE m i=1 T t=1 l j i,t (x i,t ) - m i=1 T t=1 l j i,t (x ⋆ ) ≤ log(d) 16ε. Assume without loss of generality these sequences are S 1 , . . . , S d/2 . Let B j be the set of outputs that has low regret on S j , that is,B j = (x 1,1 , . . . , x m,T ) ∈ [d] mT : m i=1 T -k+1 t=1 ℓ j (x i,t ) ≤ log(d) 8ε .Note that B j ∩ B j ′ = ∅ since if x 1:m,1:T ∈ B j then among the mk outputs x 1:m,T -k+1:T at least3mk 4 = 3 log(d) 8εof them must be equal to j. Now Markov inequality implies thatP A S j ∈ B j ≥ 1/2.Moreover, group privacy givesP A S j ∈ B j ′ ≥ e -mkε P A S j ′ ∈ B j ′ -mkδ ≥ 1 2 √ d - log d 2ε δ ≥ 1 4 √ dwhere the last inequality is due to δ ≤ ε/d. Overall we get thatd/2 -1 4 √ d ≤ P A S j / ∈ B j ≤ 1 2which is a contradiction for d ≥ 32.Fed-SVT contains a client-side subroutine (Algorithm 7) and a server-side subroutine (Algorithm 8). if t == nN for some integer n ≥ 1 then 5:Communicate to server:t-1 t ′ =t-N l i,t ′ (x) 6:Receive from server: x t 7: if t == nN for some integer n ≥ 1 then 5:Receive from clients:t-1 t ′ =t-N l i,t ′ (x) 6: if k < κ then 7: Server defines a new query q t = m i=1 t-1 t ′ =τ l i,t ′ (x t ′ ) 8: Let γ t = Lap 8 ε 9: if q t + γ t ≤ L then 10:Communicate to clients: x t = x t-1 11: else 12: Sample x t with scores s t (x) = max m i=1 t-1 t ′ =1 l i,t ′ (x t ′ ), mL ⋆ for x ∈ [(d) √ log( 1 δ )+log T 2 N 2 ρ log( d ρ ) mε + (N + L ⋆ ) log d ρ .Proof. DP guarantee: There are κ applications of exponential mechanism with privacy parameter η. Moreover, sparse vector technique is applied over each sample once, hence the κ applications of sparse-vector are ε/2-DP. Overall, the algorithm is (ε/2 + κη)-DP and (ε/2 + 2κ log(1/δ)η + κη(e η -1), δ)-DP (Lemma 14). Setting η = ε/2κ results in ε-DP and η = ε/ κ log(1/δ) results in (ε, δ)-DP.The number of communication between the central server and clients scales in O(mT /N ). Moreover, within each communication, the number of scalars exchanged scales in O(d). Therefore the communication cost is O(mdT /N ).Regret upper bound: We define a potential at phase n ∈ [T /N ] :ϕ n = x∈[d] e -ηLn(x)/2where L n (x) = max m i=1nN -1 t ′ =1 l i,t ′ (x), mL ⋆ . Note that ϕ 0 = de -ηmL ⋆ /2 and ϕ n ≥ e -ηmL ⋆ /2 for all n ∈ [T /N ] since there is x ∈ [d] such that m i=1 T t=1 l i,t (x) ≤ mL ⋆ . We split the iterates to s = ⌈log d⌉ rounds n 0 N, n 1 N, . . . , n s N where n p is the largest n ∈ [T /N ] such that ϕ np ≥ ϕ 0 /2 p . Let Z p be the number of switches in [n p N, (n p+1 -1)N ] (number of times the exponential mechanism is used to pick x t ). Let Z = s-1 p=0 Z p be the total number of switches. Note that Z ≤ 3s + s-1 p=0 max (Z p -3, 0) and Lemma 12 implies max (Z p -3, 0) is upper bounded by a geometric random variable with success probability 1/3. Therefore, using concentration of geometric random variables (Lemma 13), we get that P (Z ≥ 3s + 24 log(1/ρ)) ≤ ρ.Since K ≥ 3s + 24 log(1/ρ), the algorithm does not reach the switching budget with probability 1-O(ρ). So the total number of switching scales as O(log(d/ρ)). Now we analyze the regret. Define T 1 N, . . . T C N as the switching time steps with T C N = T , where C = O(log(d/ρ)). Lemma 16 implies that with probability at least 1 -ρ,EQUATIONCase 1: Setting η = ε/2κ in Equation ( 8), we havem i=1 T t=1 l i,t (x i,t ) ≤ O mL ⋆ log d + log 2 d + log(T 2 /(N 2 ρ)) log(d/ρ) ε + mN log(d/ρ) .Case 2: Setting η = ε/ κ log(1/δ) in Equation ( 8), we havem i=1 T t=1 l i,t (x i,t ) ≤ O mL ⋆ log d + log 3/2 d log(1/δ) + log(T 2 /(N 2 ρ)) log(d/ρ) ε + mN log(d/ρ) .Lemma 12. Fix 0 ≤ p ≤ s -1. Then for any 1 ≤ k ≤ T /N , it holds thatP (Z p = k + 3) ≤ (2/3) k+2 < (2/3) k-1 (1/3).Proof. Let n p N ≤ nN ≤ n p+1 N be a time-step when a switch happens (exponential mechanism is used to pick x t ). Note that ϕ np+1 ≥ ϕ n /2. We prove that the probability that x t is switched between nN and n p+1 N is at most 2/3. To this end, note that if x t is switched beforen p+1 N then m i=1 np+1N -1 t ′ =nN l i,t ′ (x t ′ ) ≥ L -8 log(2T 2 /(N 2 ρ)) ε , therefore L np+1 (x) -L n (x) ≥ L -8 log(2T 2 /(N 2 ρ)) ε ≥ 4/η. Thus we have that P (x t is switched before n p+1 N ) ≤ x∈[d] P (x t = x) 1 L np+1 (x) -L n (x) ≥ 4/η = x∈[d] e -ηLn(x)/2 ϕ n • 1 L np+1 (x) -L n (x) ≥ 4/η ≤ x∈[d] e -ηLn(x)/2 ϕ n • 1 -e -η(Ln p+1 (x)-Ln(x))/2 1 -e -2 ≤ 4/3 1 -ϕ np+1 /ϕ n ≤ 2/3.where the second inequality follows the fact that 1{a ≥ b} ≤ 1-e -ηa 1-e -ηb for a, b, η ≥ 0, and the last inequality since ϕ np+1 /ϕ n ≥ 1/2. This argument shows that after the first switch inside the range [n p N, n p+1 N -1], each additional switch happens with probability at most 2/3. So we have P (Z p = k + 3) ≤ (2/3) k+2 < (2/3) k-1 (1/3).The simulations were conducted on a system with a 2.3 GHz Dual-Core Intel Core i5, Intel Iris Plus Graphics 640 with 1536 MB, and 16 GB of 2133 MHz LPDDR3 RAM. Approximately 10 minutes are required to reproduce the experiments.We present our numerical results with different seeds in Figure 4 and Figure 5 .We use the MovieLens-1M dataset (Harper and Konstan, 2015) to evaluate the performances of Fed-SVT, comparing it with the single-player model Sparse-Vector (Asi et al., 2023) . We first compute the rating matrix of 6040 users to 18 movie genres (experts) R = [r u,g ] ∈ R 6040×18 , and then calculate L = [max(0, r u,g ⋆ -r u,g )] ∈ R 6040×18 where g ⋆ = arg max g 1 6040 6040 u=1 r u,g . We generate the sequence of loss functions {l u } u∈ [6040] where l u = L u,: . In our experiments, we set m = 10, T = 604, ε = 10, δ = 0 and run 10 trials. In Fed-SVT, we experiment with communication intervals N = 1, 30, 50, where communication cost scales in O(mdT /N ). The per-client cumulative regret as a function of T is plotted in Figure 6 . Our results show that Fed-SVT significantly outperforms Sparse-Vector with low communication costs (notably in the N = 50 case). These results demonstrate the effectiveness of our algorithm in real-world applications. The "Report Noisy Max" mechanism can be used to privately identify the counting query among m queries with the highest value. This mechanism achieves this by adding Laplace noise independently generated from Lap(∆/ε) to each count and subsequently determining the index corresponding to the largest noisy count (we ignore the possibility of a tie), where ∆ is the sensitivity of the queries. Report noisy max gives us the following guarantee. Lemma 15 (Dwork et al. (2014) , Claim 3.9). The Report Noisy Max algorithm is ε-differentially private.We recall the sparse-vector technique here. Given an input S = (z 1 , . . . , z n ) ∈ Z n , the algorithm takes a stream of queries q 1 , q 2 , . . . , q T in an online manner. We assume that each q i is 1-sensitive, i.e., |q i (S) -q i (S ′ )| ≤ 1 for neighboring datasets S, S ′ ∈ Z n that differ in a single element. We have the following guarantee. Lemma 16 (Dwork et al. (2014), Theorem 3.24) . Let S = (z 1 , . . . , z n ) ∈ Z n . For a threshold L and ρ > 0, there is an ε-DP algorithm (AboveThreshold) that halts at time k ∈ [T + 1] such that for α = 8(log T +log(2/ρ)) ε with probability at least 1 -ρ, we have q i (S) ≤ L + α for all t < k, and q k (S) ≥ L -α or k = T + 1.This work improves online learning and decision-making through collaboration among multiple users without exposing personal information, which helps balance the benefits of big data with the need to protect individual privacy, promoting ethical data usage and fostering societal trust in an increasingly data-driven world.We provide some applications of differentially private federated OPE in Appendix B.We don't consider adaptive adversaries in this work because they can force DP algorithms to incur a linear regret, specifically when ε ≤ 1/10 for ε-DP (Theorem 10 inAsi et al. (2022b)).We note that our definition is slightly different from that inAsi et al. (2022b), where the loss functions are explicitly dependent on a sequence of variables zi, . . . , zT ∈ Z. This is because we focus on stochastic and oblivious adversaries in this work, and our definition is essentially equivalent to that inAsi et al. (2022b) for those cases. 


Decision: This paper studies the problems of differentially private federated online prediction from experts against both stochastic adversaries and oblivious adversaries. 

All the reviewers agree the current paper provide interesting theoretical results and that the authors have successfully addressed most of the reviewers' concerns. In light of this, I recommend acceptance and encourage the authors to include additional experimental results to further validate the proposed methods in the revision.

Reviews: review: paper_summary: paper_summary: The paper studies the problems of differentially private federated online prediction from experts against both stochastic adversaries and oblivious adversaries. The main contributions are three-fold. First, for stochastic adversaries, the paper proposes a differentially private mixture of experts algorithms and provide theoretical guarantees along with. Besides, for oblivious adversaries, the paper first shows a pessimistic result by providing a lower bound showing that federated learning cannot improve over the single machine learning in general. Furthermore, the paper shows that under special realizable case, however, federated learning can benefit from more machines. The paper proposes an algorithm that achieves that benefit with theoretical guarantees.
strength_weakness: strength_weakness: My only concern of the paper is on the application side. While the problem studied by the paper makes perfect sense from a theoretical perspective, it does not seem very clear to me where it can have applications. With that being said, I think it is fine for authors to focus on a theoretical problem and leave its potential applications for future work.
questions: questions: Would you please list some potential applications of the proposed algorithms? It will be better to have some specific applications for readers to keep in mind.
limitations: limitations: Like admitted by the authors and pointed out in the weakness section, the main limitation of the paper is the lack of real-world data experiments and applications. But given the theoretical nature of the paper, I do not think this limitation is unacceptable.
paper_summary: paper_summary: This paper studies differentially private federated online prediction from experts against stochastic and oblivious adversaries. The goal is to minimize average regret across clients over time with privacy guarantees. For stochastic adversaries, the proposed Fed-DP-OPE-Stoch algorithm achieves regret improvement over single-player counterparts with logarithmic communication costs. For oblivious adversaries with a low-loss expert, the new Fed-SVT algorithm demonstrates an m-fold regret speed-up under pure and approximate differential privacy, nearly optimal up to logarithmic factors according to established lower bounds. Simulation experiments have been done.
strength_weakness: strength_weakness: 1, Lack of Real-World Evaluation: The lack of experiments on real-world dataset scenarios is a significant limitation. The authors should address how their proposed algorithms would perform and be applicable to practical problems in domains like recommender systems or healthcare. Without evaluations on real-world datasets, it is challenging to judge the practical utility and potential challenges of their methods.

2, Novelty Concerns:  After given a tree-based method is used for private aggregation of the gradients of loss functions (Asi et al., 2021b), what's the challenge for the theoretical analysis of proposed algorithms given Asi et al., 2022b and Asi et al., 2023?
questions: questions: 1, Please add at least one experiment with real-world dataset. So reader can have better sense regarding the real-world application and how practical of the proposed algorithms.
2, Please clarify the challenges in theoretical analysis given existing methods.
limitations: limitations: None
paper_summary: paper_summary: The paper studies the problem of online federated expert selection. In order to make the proposed algorithm robust against adversaries, the paper proposes algorithms with differential privacy guarantees. Both stochastic and oblivious adversaries are investigated by the paper. The paper provides theoretical guarantees for the proposed algorithms. The paper provides experimental results to verify theoretical findings.
strength_weakness: strength_weakness: 1. The paper can benefit from extending its experimental study. It would be great if authors can add more datasets and also do more ablation studies to strengthen the contribution of the paper.
2. The paper can add more explanations about applicability of the study. Usually federated learning is used to train a model. However, reading the paper, the practical applications of the paper is not obvious.
questions: questions: 1. I do not understand the statement in the paper that "*In the federated setting, it is infeasible for the central server to have full access to past loss functions due to the high communication cost.*" I think in these cases the server can collect losses over time and store them in such a way that clients can afford communication cost. I believe in these cases probably storage can be more important bottleneck than communication cost. Furthermore, I do not think sending a loss would be bottleneck for the system in both communication and storage aspects even if the number of clients is large. Can you explain more about this?
2. I suggest extending the literature review of the paper by including the work "Personalized online federated learning with multiple kernels. *Advances in Neural Information Processing Systems (NeurIPS)*, 35:33316–33329, 2022.". This work studies online model selection for communication and prediction efficiency in online federated learning.
limitations: limitations: The paper discusses the limitations adequately. For example, the paper clearly presents the assumption in section 3 that the loss functions are assumed to be convex and smooth with respect to $||\cdot||_1$.
paper_summary: paper_summary: The paper addresses the problem of online prediction from experts (OPE) under differential privacy (DP) constraints in a federated setting. OPE operates in a set of rounds, and consists on choosing at each round the expert that minimizes the regret over observations of data. The selection of the expert at each round is based on previous adversarially chosen observations of data. Differentially private OPE (DP-OPE) ensures that the selection of experts is not significantly different (up to $\epsilon$ and $\delta$ parameters) if one observation of the data changes. 

The current protocol studies private OPE in the federated setting (Fed-DP-OPE), where the expert selection is done by a set of clients that collaborate via a server. Under local DP (i.e. all messages between server and clients are part of the output of the protocol) and $m$ clients, the current work provides fundamental bounds of over the impact of the federated collaboration on the regret. First, it proposes a protocol that achieves an order-wise $\sqrt{m}$ multiplicative regret reduction with respect to DP-OPE when the adversarial observations are chosen randomly. Second, it shows that the communication cost is logarithmic in the number of expert selection rounds. Third, it shows that under an oblivious adversary that chooses the the observations arbitrarily in advance, it is not possible to obtain an order-wise improvement regret in Fed-DP-OPE over DP-OPE. Finally, it shows that improvement is possible in the federated setting for a relaxation of the oblivious adversary.
strength_weakness: strength_weakness: There are certain non-major weaknesses in motivating the problem and clarity at preliminaries:  

1- The implications of accurate OPE could be better motivated in the introduction. 

2- The notion of DP in the online setting could be better clarified. First, a link between the chosen sequence of loss functions and possibly sensitive data is missing. Second, the definition specifies "DP against an adversary". The same terminology for DP adversary and OPE adversary in charge of selecting observations over the sensitive dataset is confusing.
questions: questions: Could you please clarify what is the link between sensitive data and the notion of neighboring input used in the paper? 

For instance, it would seem reasonable that the sequence $\mathcal{S}$ of loss functions chosen by the adversary depend on a set of sensitive data points. Then, it could be possible that more than one loss function changes if a single entry of this dataset changes. However, your setting is a bit different and I am wondering where could it be applicable.
limitations: limitations: The limitations of the work have been appropriately addressed by the authors.

Comments: title: Thank You for Your Helpful Feedback
References
comment: Thank you so much for your positive feedback! Your insightful comments have helped us make our work better. We really appreciate it.
Dear authors,

Thank you for successfully addressing my (non-major) concerns in your rebuttal. 

I have no further questions and my score is likely to remain unchanged.
Thank you very much for your positive feedback! Your valuable input has helped us improve the quality of our work significantly. We really appreciate it.
Thank you for responding. I read the rebuttal and it addressed my second concern regarding novelty. I increased my score from 5 to 6.
Thank you for taking the time to review our rebuttal. We’re glad to hear that we addressed some of your concerns and that your overall assessment is in favor of accepting the paper.

We understand your point regarding the experimental study. Due to time constraints, we were only able to conduct experiments on MovieLens dataset during rebuttal. We will certainly include additional experimental results in the revision.

Thank you again for your feedback, and we are happy to address any further questions you might have.
Thank you for responding to my comments. I read the rebuttal and it addressed part of my concerns. However, I believe the experimental study of the paper can still be extended and improved. I would maintain my initial rating which is in overall in favor of accepting the paper.
Dear Reviewer hhm9,

We've taken your initial feedback into careful consideration in our response. Could you please check whether our responses have properly addressed your concerns? We are more than happy to answer your further questions.

Thank you for your time and effort in reviewing our work!

Best Regards,

Authors
Dear Reviewer H7Yw,

We've taken your initial feedback into careful consideration in our response. Could you please check whether our responses have properly addressed your concerns? We are more than happy to answer your further questions.

Thank you for your time and effort in reviewing our work!

Best Regards,

Authors
Dear Reviewer NyWa,

We've taken your initial feedback into careful consideration in our response. Could you please check whether our responses have properly addressed your concerns? If so, could you please kindly consider increasing your initial score accordingly? Certainly, we are more than happy to answer your further questions.

Thank you for your time and effort in reviewing our work!

Best Regards,

Authors
Dear Reviewer RFE1,

We've taken your initial feedback into careful consideration in our response. Could you please check whether our responses have properly addressed your concerns? If so, could you please kindly consider increasing your initial score accordingly? Certainly, we are more than happy to answer your further questions.

Thank you for your time and effort in reviewing our work!

Best Regards,

Authors
We thank the reviewer again for the helpful comments and suggestions for our work. If our response resolves your concerns to a satisfactory level, we kindly ask the reviewer to consider raising the rating of our work. Certainly, we are more than happy to address any further questions that you may have.
[1] Li X, Huang K, Yang W, et al. On the convergence of fedavg on non-iid data[J]. arXiv preprint arXiv:1907.02189, 2019.

[2] Shahid O, Pouriyeh S, Parizi R M, et al. Communication efficiency in federated learning: Achievements and challenges[J]. arXiv preprint arXiv:2107.10996, 2021.

[3] McMahan B, Moore E, Ramage D, et al. Communication-efficient learning of deep networks from decentralized data[C]//Artificial intelligence and statistics. PMLR, 2017: 1273-1282.

[4] Smith V, Chiang C K, Sanjabi M, et al. Federated multi-task learning[J]. Advances in neural information processing systems, 2017, 30.

[5] Sattler F, Wiedemann S, Müller K R, et al. Robust and communication-efficient federated learning from non-iid data[J]. IEEE transactions on neural networks and learning systems, 2019, 31(9): 3400-3413.

[6] Yang T, Mahdavi M, Jin R, et al. Online kernel selection: Algorithms and evaluations[C]//Proceedings of the AAAI Conference on Artificial Intelligence. 2012, 26(1): 1197-1203.

[7] Zhang X, Liao S, Xu J, et al. Regret bounds for online kernel selection in continuous kernel space[C]//Proceedings of the AAAI Conference on Artificial Intelligence. 2021, 35(12): 10931-10938.

[8] Ghari P M, Shen Y. Graph-aided online multi-kernel learning[J]. Journal of Machine Learning Research, 2023, 24(21): 1-44.

[9] Ghari P M, Shen Y. Online multi-kernel learning with graph-structured feedback[C]//International Conference on Machine Learning. PMLR, 2020: 3474-3483.

[10] Hong S, Chae J. Communication-efficient randomized algorithm for multi-kernel online federated learning[J]. IEEE transactions on pattern analysis and machine intelligence, 2021, 44(12): 9872-9886.

[11] M Ghari P, Shen Y. Personalized online federated learning with multiple kernels[J]. Advances in Neural Information Processing Systems, 2022, 35: 33316-33329.

[12] Ghari P M, Shen Y. Budgeted Online Model Selection and Fine-Tuning via Federated Learning[J]. arXiv preprint arXiv:2401.10478, 2024.

[13] Mannor S, Shamir O. From bandits to experts: On the value of side-observations[J]. Advances in Neural Information Processing Systems, 2011, 24.

[14] Cohen A, Hazan T, Koren T. Online learning with feedback graphs without the graphs[C]//International Conference on Machine Learning. PMLR, 2016: 811-819.

[15] Alon N, Cesa-Bianchi N, Dekel O, et al. Online learning with feedback graphs: Beyond bandits[C]//Conference on Learning Theory. PMLR, 2015: 23-35.

[16] Cortes C, DeSalvo G, Gentile C, et al. Online learning with dependent stochastic feedback graphs[C]//International Conference on Machine Learning. PMLR, 2020: 2154-2163.

[17] Ghari P M, Shen Y. Online learning with uncertain feedback graphs[J]. IEEE Transactions on Neural Networks and Learning Systems, 2023.

[18] Esposito E, Fusco F, van der Hoeven D, et al. Learning on the edge: Online learning with stochastic feedback graphs[J]. Advances in Neural Information Processing Systems, 2022, 35: 34776-34788.

[19] Ghari P M, Shen Y. Online learning with probabilistic feedback[C]//ICASSP 2022-2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 2022: 4183-4187.