Federated Online Prediction from Experts with Differential Privacy: Separations and Regret Speed-ups
Authors: Fengyu Gao
Ruiquan Huang
Jing Yang
Venue: NeurIPS 2024 poster (2024)
Keywords: online learning
federated learning
differential privacy
Primary area: privacy

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.

Federated Online Prediction from Experts with Differential Privacy: Separations and Regret Speed-ups
Fengyu Gao, Ruiquan Huang, Jing Yang School of EECS, The Pennsylvania State University, USA (fengyugao, rzh5514, yangj mangjin]>e @psu. edu
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 parallel over time horizon with explicit differential privacy (DP) guarantees. With stochastic adversaries, we propose Ped-DP-OPE-Stoch algorithm that achieves /mmfoold speed-up of the per-client regret compared to the single- -llyeer 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 regrel speed-up with general oblivious adversaries. We then consider 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.
1 Introduction
Federated Learning (FL) (McMahan al. 2017) is 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 al.) [2023] Gauthier et al.) (023). Noticeable advancements include various algorithms in federated multi-armed bandits (Shi et al. [202]] Huang
al.
202 Li and Wang 2022 Yi and Vojnovic 2022 (003). federated online convex optimization
Patel et al. 2023 K Kwn 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. 20206 /hu et al.
2021 Dubey and Pentland] 2022) and linear contextual bandits (Dubey and Pentland 2020 [ al.
2022a Zhou and Chowdhury (0233] Huang et al. 2023), to the best of our knowledge, federated online learning in the adversarial setting with DP considerations remain largely unexplored.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

In this work, we focus on federated online prediction from experts (OPE) with rigorous differential privacy (DP) guaramtees] OPE (Arora et al., 2012) is a classical online learning problem under which, a player chooses one out of set of experts at each time slot and an adversary chooses loss function. The player incurs 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 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 sequence of loss functions in advance.
When 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 Vojnovie 2023). Specifically, we aim to answer the following question:
Can we design differentially private federated OPE algorithms to achieve regret speed-up 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-eficeeee
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 '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 Bedd-D--PPE-Strr achieves 1/ /m-ffldd reduction of the per-client regret compared to the single-player counterparts (Asi et al. (022b) 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 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- non-trivial challenge, because it requires envisioning scenario where the collaborative nature of FL does not lead 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 Fe that obtains near-optimal regret when there is low-loss expert. We show that Fed-SVT achieves an mn-old 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 nearly optimal up to logarithmic factors.
'e provide some applications differentially private federated OPE Appendix "e don't It consider adaptive adversaries in this work because they can force DP algorithms to incur linear regret, specifically when & 1/10 for DDP (Theorem 10 in Asi et al. (002b)).

---

Table 1: Comparisons for Online Prediction from Experts under DP Constraints
Advensines
Algoricam (Keterence)
Kegret
Communication cost
Stochastic
Limited Updates et
2122
SING c-DR (r,6)-DP
Plnga
Iopalio
Ped-DP-CPPE.soch (Corollary 1
FED
cDDR (e,6)-DP
Floga
O (nudlnng))
Sparse-Vectoo Asi et
2023
Oblivious (Realizable)
Fad-SVT (heorem
FED
c-DP
N Mlogd
(maTT)N)
Sparse Vector Asi et al.
2023
SING
(r.0).DP
Fed-SVI (Theorem
FED
(s,6)-DP
0
lor G-tog
log
(mndT//V
Lower bound (Theorem 3
FED
cDDR (c,6)-DP
Q
Oblivious
Lower bound (Theorem
FED
cDDR (s.6)-DP
min
number of clients; T: time horizon; d: number experts: 6: DP parameters: SING and FED stand for single-elient and foderated
setlings, respectively.
summary of our main results and how they compare with the state of the is shown in Table comprehensive literature review is provided in Appendix A
2 Preliminaries
Federated online prediction from experts. Federated OPE consists of central server, m clients and an interactive T T-round game between an adversary and an algorithm. At time step t, each client E [m] first selects an expert Ji,t E [d], and then, the adversary releases loss function 1i, Stochastic adversaries choose a distribution over loss functions and sample sequence of loss functions/ ., Im, an IID fashion from this distribution, while oblivious adversaries choose sequence of loss functions (,,1...., 4m,, at the beginning of the game.
For federated OPE, the utility of primary interest is the expected cumulative regret among all clients defined as:
T
Reg(T, m) m
1
Σ
(a( min x Eld]
ΣΣ l,c(a*) t=1
Differential privacy. We define differential privacy in the online setting following (Dwork et al. 2010). If an adversary chooses a loss sequence S the output of the interaction between the federated online algorithm A and the adversary. We say = (I1.1...., .m,r) and S' = ( !m,,)) are neighboring datasets if S and S' differ in one element.
".i.....,m,,7) we denote A(S)
Definition ((e, -)-DP). A randomized federated algorithm A is (e, d)-differentially private against an adversary if, for all neighhoring datasets S and S' and for all events O in the output space of A, we have
P[A(S) 0) < EF E 8
Communication model. Our setup involves a central server facilitating periodic communication with zero latency with all clients. Specifically, the clients 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 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.
3 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 the single-player setting under DP constraints with low
We note that our definition is slightly different from that Asi et al. (202b)), where the loss functions are explicitly dependent on a sequence of variables &, 27 E 2. This is because we focus on stochastic and oblivious adversaries in this work, and our definition is essentially equivalent to that in Asi et al. (202bb) for those cases.
3

---

communication cost. We consider the loss functions ... to be convex, a-Lipschitz and f-smooth w.n.t. || this section.
3.1 Intuition behind Algorithm Design
To gain better understanding of our algorithm design, we first elaborate the difficulties encountered when extending prevalent OPE models to the FL. setting under DP constraints. worth noting that all current OPE models with stochastic adversaries rely on gradient-based optimization methods. The central task in designing OPE models with stochastic adversaries lies in leveraging past loss functions to guide the generation of expert predictions. Specifically, we focus on the prominent challenges associated with the widely adopted woonk-Wolfe-baee methods (Asi et al.) 2022b). This algorithm iteratively moves the expert selection 2, towards point that minimizes the gradient estimate derived from the past loss functions .,..... 4-1 over the decision space X. where X' =
As { E Rd 2, 2 0, Ei= 2, = 1]. and each E X' represents probability distribution over d experts. With DP constraints, tree-based method is used for private aggregation of the gradients of loss functions (Asi et al., 2021b).
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. To overcome this, we use design of local loss function gradient estimation for global expert determination. Our solution involves locally estimating the gradient of each client's 's loss functions, and then communicating these estimates the server, which globally generates 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 crucial as it extends beyond privatizing the selection of experts: ensures the privacy of all information exchanged between the central server and clients within the FL framework.
3.2 Algorithm Design
To address the aforementioned challenges, we propose the Fed-DP-OPE-Stoch algorithm. The -PP--SP- algorithm works in phases. In total, it has P phases, and each phase p E [P] contains 2--1 time indices. Red-DP-OPE-SO server-side subroutine (Algorithm 2} The framework of our algorithm is outlined as follows.
contains a client-side subroutine (Algorithm [ and
At the initialization phase, the server selects arbitrary point X and broadcasts all clients. Subsequently, each client initializes its expert selection I;, = z, pays cost 4,, (I1,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 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 Bi,-- = (4,22-2,.... ...,,4,22 24.2-1111 We employ the tree mechanism for the private aggregation at each client, as 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 DP-FW subroutine at each client i, with sample set B. parameter Ti and batch size In DP-FW, each vertex in the binary tree j corresponds to gradient estimate u.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 in Appendix C.1
Intuitively, in the DP-FW subroutine, reaching a leaf vertex marks the completion of gradient refinement for 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 of tree j. each client sends the server a set of noisy inner products for each decision set vertex

---

On with their gradient estimate Vtj.s. In other words, each client communicates with the server by sending (le, 1s.g.a) + Si,n Ine]g. where CI....,C represents d vertices of decision A.- S.m Lap(Aes,s). and Xi.ja 402!
Private Global Expert Prediction. After receiving {(e, Weg.s) + Sin from clients, the central server privately predicts new expert:
Wisa arg min
Σ 2=1
((on Vigga) + Sim)
ca InnS
Subsequently, the server broadcasts the "global prediction" Wyee 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 w.s. each client updates its expert prediction for leaf k 1, denoted as Ltppk+1 E X, as follows:
Tipp = (1 R....)) + Thppk
where 1/.pp 1++11
2
After updating all leaf vertices of the trees, the client obtains Ki the final state of the expert prediction in phase p. Then, each client sticks with expert selection Zt.pKK throughout phase p and collects loss functions 4,22 ..... 2 ( The key difference between Fed-DP-OPE-Stoch and
Remark (Comparison with Asi 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 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 the local level in our algorithm distinguishes it from non-federated approaches.
Algorithm Fed-DP DEE-D-P-PE-SOOOo Client
1: Input: Phases P, trees Ti, decision set = Aa with vertices (cI...., ca), batch size b.
2: Initialize: Set 2i,1 E X' and pay cost 44,1 (32,1)-
3: for 2 to do
4: Set B,, (4,20-2,... 14, 1.2201113
5: Set k = and Tt = Zi,p-1, 1,K
6: ( (0)
DP-FW (Bi,p Ti,
7:
for all leaf vertices reached in DP-FW do
8:
Communicate to server: {cn, Pt.j.a) + tin where Ein Lap(ds...)
9: Receive from server: j.ss
Update Zi,p. according to Equation
11: Update k = k
end for
13:
Final iterate outputs Ki.p.
14: for t = 2P-1 to 2 do
Receive loss 4,e X' - and pay cost 4 (xt.p.)
16: end for
end for
3.3 Theoretical Guarantees
Now we are ready to present theoretical guarantees for Fed-DP-OPE-Stoch.
Theorem 1. Assume that loss function 4..(-) is convex, a-Lipschitz, 3-smooth w.r. || - Setting
2 20-1
Ped-DP-OPE-Stoch (i) satisfies sDDP and (ii) (p- and log alog
be
achieves the per-client regret of
(1a+ ())
Tlog d m
2Bp log d log
m V
5

---

Algorithm 2 Fedd-D--OPE-Stoch: Central server
1: Input: Phases P, number of clients decision set X = A with vertices .ci,..., Cat.
2: Initialize: Pick any 2 E X and broadcast to clients.
3: for to P do
4: Receive from clients: {(en, Wt.j.s) + Si,n In(dd)
5: Update W3 according to Equation
6: Communicate to clients: Wj,
7: end for
with (it) a communication cost of O (mid,
log
A similar result characterizing the performance of Fed-DP-OPE-Stoche under (s, 6)PP) constraint is shown in Theorem 6
Proof sketch of DP guarantees and communication costs. Given neighboring datasets S and S' dif- fering ligtt "n we first note that 14 i is used only one phase, denoted p1- Furthermore, note that l,,,,, or i,,,,, is used in the gradient computation for at most 2/ iterations, corresponding to descendant leaf nodes. This insight allows to set noise levels Ar,, sufficiently large ensure each of these iterations E e/2i- e/2i-IsI_DP regarding output (cn, Ut, .j.) [ee(d By basic composition and post-processing, we can make sure the final output is e-DP.
The communication cost is obtained by observing that there are p phases, and within each phase, there are O(24)) leaf vertices. Thus, the communication frequency scales 0 2 and the communication cost scales in ((md) E, ).
Proof sketch of regret upper bound. We first give bounds for the total regret in phase p [P]. We can show that for every in phase p. we have
Tx( & Tue (1t.p))) + T.p. (T. - Tee (xte..)) N.p. V - 0pp
+ ni,p
(Dp.te Wp.k)
min (Tp,kr w)) mm.mk. wEX
To upper bound the regret, we bound the following two quantities separately.
Step bound V L. Up.x:loo in Lemma We show that every index of the d-dimensional
vector (... - pp,x k is O +.3"
bm usuu-Gaussian by induction on the depth of vertex in Lemma
Therefore, E [TI [loo is upper bounded by O (a 3) log
Step bound (5p.k. Wp.)) min(0, (Up.ks we in Lemma wEx
establish that (Tp.ks (p.k)
Σ Eim This bound incorporates the maxi- mum absolute sum of m IID Laplace random variables Ei,--
weX min (Tp. w) is upper bounded by 2 max m Sii
To quantify the bound on the Consequently, have
sum of IID Laplace random variables, refer Lemma 4
(unn, w) upper bounded by O Arsiee Ind Vm
(Tp,ks wp.k)
wEx
With the steps above, we can show that for each time step in phase p, ([L((Z),,k) Lo(x*)]
upper bounded by O (a + B)
logd 2pm
Vo log
Summing up all the phases gives us the final
m V2PS
upper bound. The full proof of Theorem
T can be found in Appendix C.2
When 3 is small, Theorem reduces to the following corollary.

---

Corollary 1. If 3 O
then, Fed-DP-OPE-Stoch (i) satisfies E-DP and (ii) achieves the vmileh
log
per-client regret of
Reg(T", m) =0 o( @
(V
log log d vmme
with (iii) a communication cost of O (md log
The full proof of C be found in Appendix C.2
Remark 2. We note that the regret for the single-player counterpart Asi et al. (2022b) scales in
O VTlogd d + log digdlog"" when 5 = O Te Compared with this upper bound, Red-DP-OPE
Stoch achieves v /m-ffldd speed-up. with communication cost of O(md log T). 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 private algorithm, assuming client- 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 Appendix C.4 and the theoretical guarantees are provided in Theorem 7
OP-OPE--toor can be slightly modified into a centrally differentially
C.4
4 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 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 Q(vT log d). Let E (0, and o(L/TT), for any (e, federrate algorithm, the per-client regret is lower bounded by Ω min
federated OPE
(Ladd.))
log )))
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 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 when all clients receive the same loss function from the oblivious adversary at each time step, i.c. 4it 14. Within this framework, we define the "average policy" among all clients, i.e., [k(
>m -i=1 (k), Vk E [d]. This leads us to express the per-client regret as: Reg(T', m) ΣT Ex (k(K)) ((()) Σt= ((*), Note that (k) is detined by (k.(k),..... .P.)).....PP.(( (k), which in turn are determined by 11,1...,, -mm.-1- According to our choice of 4,, V, p((()) determined by L KK,..... 14.....44,, Therefore, 1/ .p....../ are generated by 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 useful in future analysis of other FL algorithm. Incorporating DP constraints, refer to Lemma 9 which transforms the DP
7

---

online learning problem to a well-examined DP batch model. The full proof of Theorem 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, there any special scenarios where we can still hurness the power of federation even in presence of oblivious adversaries? Towards this end, in this section, focus the (near) realizable setting, formally defined below.
Definition (Realizability). federated OPE problem is realizable there exists a feasible solution xx E [d] such that Σi=1 (1,((**) = O, Vi E [m]] If the best expert achieves small loss L < T, i.e., there exists x² E [d] such that Σt=1 (,,(x*) S I", Vi E [m]] the problem is near-realizable.
Intuitively, collaboration 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 sparse vector based federated algorithm can almost achieve such lower bounds thus is nearly optimal.
5.1 Lower Bound
Theorem 3. Let S 1 and 8 S e/d. For any (s, DD-P federated OPE algorithm against oblivious log(d)
adversaries in the realizable setting, the per-client regret is lower bounded by S2
Remark 5. In the single-player setting, the regret bound is Ω
log(d)
Asi et al. 2023). In the
federated setting, results imply that the per-client regret is reduced to m times the single-player regret. This indicates a possible m-fold speed-up in the federated setting.
Proof sketch. To begin, consider specific oblivious adversary. We introduce prototype loss functions: (xx) 0 for all x E [d] and for j E [d] (z()) = if = and otherwise (xx) 1. An oblivious adversary picks one of the sequences S , 5 uniformly at random,
where S = ...
Pr m) such that 1 = if L = ,,....77 T - k, otherwise, Ki,, = 15, and Assume there exists an algorithm such that the per-client regret is upper bounded by log(d) 32m log(d)
k dogd
2me
This would imply that for at least d/2 S' S'....,S'' Sd, the per-client regret is upper bounded by 16me Assume without loss generality these sequences are $ $!....,''. Sd/2, S//2. We let B, be the set of expert selections that has low regret on St. We can show that B3 and By are disjoint for j + fj', implying
choosing any expert leads to low regret for loss sequence S¹ but high regret for S By group privacy, we have IP (A (St) E By) 2 -mkep (A (SS)) E B,,) mnô, leading to a contradiction when d 2 32. The full proof of Theorem can be found in Appendix E.]
5.2 Algorithm Design
We develop a new algorithm Fed-SVT. Our algorithm operates as follows:
Periodic communication. We adopt fixed communication schedule in our federated setting, splitting the time horizon T into T/N phases, each with length N. Fed-SVT, every client selects the same expert, i.e., Zi,t = at each time step t. Initially, each client starts with randomly chosen expert #T At the beginning of each phase ni, each client sends the accumulated loss of the last phase -1 L 4,, (z)) to the central server.
Global expert selection. The server, upon receiving ΣaN-1 1), (x) from all clients, decides whether to continue with the current expert or switch a new one. This decision grounded the Sparse-Vecth algorithm (Asi et al. 2023), where the accumulated loss from all clients over phase is treated as a single loss instance in the Sparse- Sparse-Vector algorithm. Based on the server's expert decision, clients update their experts accordingly. The full algorithm is provided in Appendix E.2
8

---

5.3 Theoretical Guarantees
Theorem 4. Let 1, E [0. 1]d be chosen by an oblivious adversary under near- realizability assumption. Fed-SVT is e-DP, the communication cost scales in O (mdT (N), and with probability at least O(p), the pre-client regret is upper bounded by x2
N2p lo)(H) + (N + L log (5)) Moreover, Fed-SVT is (s, DD- the communi- cation cost scales in O (mdT//N) and with probability at least - O(p), the pre-client regret is (N Lo)
( llg" (d)+Hog(
log (d) /igg( +log N2p log(
upper bounded by O
me
Remark 6. Note that when N + D
log
then, under Fed-SVT, the per-client regret upper
ms
bound scales in O log" d+log T log
for (e, 5)-DP. for s-DP and O log log d d-log"/2 2/2 d log((1)))
ms
Compared the best upper bound O log" d+ T log
and O
log log d+oog 8/2 dy log(1/6) for
the single-player scenario (Asi et al. 2023). our results indicate an m-fold regret speed-up. Note that our lower bound (Theorem scales in log d me
Our upper bound matches with the lower bound in terms of and e, and is nearly optimal up to logarithmic factors.
The proof of Theorem 4 is presented in Appendix E.3
Numerical Experiments
We conduct experiments in a synthetic environ- ment to validate the theoretical performances of Sodd-D-OPPE-toeeee and compare them with its ungle-player counterpart Limited Updates (Asi al. 20226).
10,
Per clent Regret
Unittdd Lnmted_pphte Updates Fes OP-OFE Stoch
20
We first generate true class distributions for each client i E [m]] and timestep E [T), which are sampled IID from Gaussian distributions with means and variances sampled uniformly. Following Gaussian sampling, we apply a softmax transformation and normalization ensure the outputs are valid probability distributions. Then we generate sequence of IID loss functions I......, b,,T for clients over 7' timesteps using cross-entropy between true class distributions and predictions. We set Ti = 1 in
5000
10000
15000
Figure 1: Per-client regret.
therefore the communication cost scales in O(md log T). We set m 10, T 2 g 10, å and 100. The per-client cumulative regret as function of T' is plotted in Figure T We see that Ddd-D--OPE-Stord outperforms Limited Updates significantly. indicating the regret speed-up due to collaboration. Results with different seeds are provided in Appendix F
Fed-SVT. We conduct experiments a synthetic environment, comparing Fed-SVT with the single-player model Sparse-Vector (Asi et al. 2023
negre
8
8
We generate random losses for each expert every timestep and for each client, ensuring that one expert always has zero loss to simulate an optimal choice. We set 10, T 29, E 10, 8 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 Sparse-Vector, 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 provided in Appendix[F Additionally, evaluate the performances of Fed-SVT on the MovieLens- 1M dataset (Harper and Konstan (015) in Appendix G
5
0
100
Figure 2: Per-client regret.
7 Conclusions
In this paper, we have advanced the ofte-ooftthearr of differentially private federated online prediction from experts, addressing both stochastic and oblivious adversaries. Our Seed----OPE-SAee algorithm

---

showcases 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--old 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.
Acknowledgments
The work of F. Gao, R. Huang and J. Yang was supported in part by the U.S. National Science Foundation under the grants
CNS-21 14542 and ECCS-2133170.
References
Agarwal, A., Foster, D. P., Hsu, D. J., Kakade, S. M., and Rakhlin, A. (2011). Stochastic convex optimization with bandit feedback. Advances in Neural Information Processing Systems, 24.
Agarwal, N., Kale, S., Singh, K., and Thakurta, A. (2023a). Differentially private and lazy online convex optimization. In The Thirty Sixth Annual Conference on Learning Theory, pages 4599 4632. PMLR.
Agarwal, N., Kale, S., Singh, K., and Thakurta, A. G. (2023b). Improved differentially private and lazy online convex optimization. arXiv preprint arX1v:2312.11534.
Agarwal, N. and Singh, K. (2017). The price of differential privacy for online learning. In Interna- fional Conference on Machine Learning, pages 32-40. PMLR.
Altschuler, J. and Talwar, K. (2018). Online learning over a finite action set with limited switching. In Conference On Learning Theory, pages 1569-1573, PMLR.
Arora, S., Hazan, E., and Kale, S. (2012). The multiplicative weights update method: meta-algorithm and applications. Theory of computing. 8(1):121-164.
Asi. H.. Chadha, K., Cheng, G., and Duchi, (2022a). Private optimization in the interpolation regime: faster rates and hardness results. In International Conference on Machine Learning, pages 1025-1045. PMLR.
Asi, H., Duchi, J., Fallah, A., Javidbakht, O., and Talwar, K. (2021a). Private adaptive gradient methods for convex optimization. In International Conference Machine Learning, pages 383-392. PMLR.
Asi. H.. Feldman, V., Koren, T., and Talwar, K. (2021b). Private stochastic convex optimization: Optimal rates in ll geometry, In International Conference on Machine Learning, pages 393-403 PMLR.
Asi, H., Feldman, V., Koren, T., and Talwar, K. (2022b). Private online prediction from experts: Separations and faster rates. arXiv preprint arXiv:2210.13537.
Asi. H., Feldman, V., Koren, T., and Talwar, K. (2023). Near-optimal algorithms for private online optimization in the realizable regime. arXiv preprint arXiv:2302.14154
Azize, A. and Basu, D. (2022). When privacy meets partial information: A refined analysis of differentially private bandits. Advances in Neural Information Processing Systems, 35:32199- 32210.
Bar-On. Y. and Mansour, Y. (2019). Individual regret in cooperative nonstochastic multi-armed bandits. Advances in Neural Information Processing Systems, 32.
Bassily, R., Feldman, V., Talwar, K., and Guha Thakurta, (2019). Private stochastic convex optimization with optimal rates. Advances in neural information processing systems, 32.
10

---

Bassily, R., Smith, A., and Thakurta, A. (2014). Private empirical risk minimization: Efficient algorithms and tight enror bounds. In 2014 IEEE 55th annual symposium on foundations of computer science, pages 464-473. IEEE.
Bubeck, S., Li, Y., Luo, H., and Wei, C.-Y. (2019). Improved path-length regret bounds for bandits. In Conference On Learning Theory, pages 508-528. PMLR.
Buccapatnam, S., Eryilmaz, A., and Shroff, N. B. (2014). Stochastic bandits with side observations networks. In The 2014 ACM international conference on Measurement and modeling of computer systems, pages 289-300.
Caron, S., Kveton, B., Lelarge, M., and Bhagat, S. (2012). Leveraging side observations in stochastic bandits. arXiv preprini arXiv: 120.4992
Cesa-Bianchi, N., Gentile, C., Mansour, Y., and Minora, A. (2016). Delay and cooperation in nonstochastic bandits. In Conference on Learning Theory, pages 605 622. PMLR.
Cesa-Bianchi, N. and Lugosi, G. (2006). Prediction, learning, and games. Cambridge university press.
Cesa-Bianchi, N., Mansour, Y., and Stoltz, G. (2007). Improved second-order bounds for prediction with expert advice. Machine Learning, 66:321-352.
Charisopoulos, V., Esfandiari, H., and Mirrokni, V. (2023). Robust and private stochastic linear bandits. In International Conference on Machine Learning, pages 4096 4115. PMLR.
Chen, L., Yu, Q., Lawrence, H., and Karbasi, A. (2020). Minimax regret of -winching-constraanedd online convex optimization: No phase transition. Advances in Neural Information Processing Systems, 33:3477-3486.
Cheng, D., Zhou, X., and Ji, B. (2023). Understanding the role of feedback in online learning with switching costs. arXiv preprint 08X.522306.09588.
Chowdhury, S. R. and Zhou, X. (2022a). Distributed differential privacy in multi-armed bandits. arXiv preprint 0rX7::2006.0577.
Chowdhury, R. and Zhou, X. (2022b). Shuffle private linear contextual bandits. arXiv:2202.05567.
arXiv preprint
Cotter, A., Shamir, O., Srebro, N., and Sridharan, K. (2011). Better mini-batch algorithms via accelerated gradient methods. Advances in neural information processing systems, 24.
Dubey, and Pentland, (2020). Differentially-prive private federated linear bandits. Advances in Neural Information Processing Systems, 33:6003-6014
Dubey, A. and Pentland, A. (2022). Private and byzantine-proof cooperative decision-making arXiv preprint arXiv:2205. 14174.
Duchi, J., Hazan, E., and Singer, Y. (2011). Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7).
Duchi, J. C.,, Chaturapruek, S., and Ré, C. (2015). Asynchronous stochastic convex optimization. arXiv preprint arXiv: 1508.00882.
Duchi. J. C., Lafferty, J., Zhu, Y., al. (2016). Local minimax complexity of stochastic convex optimization. Advances in Neural Information Processing Systems, 29.
Dwork, C., Naor, M., Pitassi. T., and Rothblum, G. N. (2010). Differential privacy under continual observation. In Proceedings of the forty-second ACM symposium on Theory of computing, pages 715-724.
Dwork, C.,, Roth, A., et (2014). The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3-4:211-4077

---

Feldman, V., Koren, T., and Talwar, K. (2020). Private stochastic convex optimization: optimal rates in linear time. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 439.
Fichtenberger, H., Henzinger, M., and Upadhyay, J. (2023). Constant matters: Fine-grained error bound on differentially private continual observation. In International Conference on Machine Learning, pages 10072-1009 PMLR.
Freund, Y. and Schapire, R. E. (1997). A decision-theoretic generalization of on-line learning and an application to boosting. Journal of computer and system sciences, 55(1):119-135
Garcelon, E., Chaudhuri, K., Perchet, V., and Pirotta, M. (2022). Privacy amplification via shuffling for linear contextual bandits. In International Conference Algorithmic Learning Theory, pages 381-407. PMLR.
Gauthier, F., Gogineni, V. C., Werner, S., Huang, Y.-F., and Kuh, A. (2023). Asynchronous online federated learning with reduced communication requirements. arXiv preprint arXiv:2303.
Geulen, S., Vöcking, B., and Winkler, M. (2010). Regret minimization for online buffering problems using the weighted majority algorithm. In COLT, pages 132-143. Citeseer.
Golowich, N. and Livni, R. (2021). Littlestone classes are privately online learnable. Advances in Neural Information Processing Systems, 34:1 1462-11473.
Gonen, A., Hazan, E., and Moran, S. (2019). Private learning implies online learning: An efficient reduction. Advances in Neural Information Processing Systems, 32.
Guha Thakurta, A. and Smith, A. (2013). (nearly) optimal algorithms for private online learning in full-information and bandit settings. Advances in Neural Information Processing Systems, 26.
Hanna, O. A., Girgis, M., Fragouli, C., and Diggavi, (2022). Differentially private stochastic linear baldits)(almost) for free. arXiv preprint arXiv:2207.0344
Harper, M. and Konstan, J. A. (2015). The moviclens datasets: History and context. Acm transactions on interactive intelligent systems (tiis), 5(4):1-19,
He, J., Wang, T., Min, Y., and Gu, Q. (2022). A simple and provably efficient algorithm for asynchronous federated contextual linear bandits. Advances in neural information processing systems, 35:4762-4477.
Hong. S. and Chae, (2021). Communication-effiice randomized algorithm for multi-kerne' online federated learning. IEEE transactions on pattern analysis and machine intelligence, 44(12):9872- 9886.
Hu, B. and Hegde, N. (2022). Near-optimal thompson sampling- algorithms for differentially private stochastic bandits. In Uncertainty in Artificial Intelligence, pages 844-852. PMLR.
Hu, C., Pan, W., and Kwok, J. (2009). Accelerated gradient methods for stochastic optimization and online learning. Advances Neural Information Processing Systems, 22.
Huang, R., Wu, W., Yang, J., and Shen, C. (2021). Federated linear contextual bandits. Advances in neural information processing systems, 34:27057-27068.
Huang, R., Zhang, H., Melis, I.,, Shen, M., Hejazinia, M., and Yang. J. (2023). Federated linear contextual bandits with user-level differential privacy. In International Conference Machine Learning, pages 14060-14095. PMLR.
Jain, P., Kothari, P., and Thakurta, A. (2012). Differentially private online learning. In Conference Learning Theory, pages 24-1. JMLR Workshop and Conference Proceedings.
Jain, P., Raskhodnikova, S., Sivakumar, S., and Smith, A. (2023). The price of differential privacy under continual observation. In International Conference on Machine Learning, pages 14654- 14678. PMLR.
12

---

Jain, P. and Thakurta, A. G. (2014). (near) dimension independent risk bounds for differentially private learning. In International Conference on Machine Learning, puges 476 PMLR.
Kalai, A. and Vempala, S. (2005). Efficiint algorithms for online decision problems. Journal of Computer and System Sciences, 71(3):9913377.
Kaplan, H., Mansour, Y., Moran, S., Nissim, K., and Stemmer, U. (2023a). Black-box differential privacy for interactive ml. In Thirty-seventh Conference on Neural Information Processing Systems.
Kaplan, H., Mansour, Y., Moran, S., Nissim, K., and Stemmer, U. (2023b). On differentially private online predictions. arXiv preprint arXiv:2302.14099
Kwon, D., Park, J., and Hong, S. (2023). Tighter regret analysis and optimization of online federated learning. IEEE Transactions on Pattern Analysis and Machine Intelligence.
Li, C. and Wang, H. (2022). Asynchronous upper confidence bound algorithms for federated linear bandits. In International Conference Artificial Intelligence and Statistics, pages 6529-6553. PMLR.
Li, C., Zhou, P., Xiong, I.., Wang. Q., and Wang, T. (2018). Differentially private distributed online learning. IEEE Transactions on Knowledge and Data Engineering. 30(8):1440-144 4453.
Li, F., Zhou, X., and Ji, B. (2022a). Differentially private linear bandits with partial distributed feedback. In 2022 20th International Symposium on Modeling and Optimization in Mobile, Ad hoc and Wireless Networks (WiOpt), pages 41-48. IEEE.
Li, F., Zhou, X., and Ji, B. (2023). (private) kernelized bandits with distributed biased feedback. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 7(1):1-47.
Li, S., Chen, W., Wen, Z., and Leung, K.-S. (2020a). Stochastic online learning with probabilistic graph feedback. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 4675- 4682.
Li, T., Song. L., and Fragouli, C. (2020b). Federated recommendation system via differential privacy. In 2020 IEEE international symposium on information theory (ISIT), pages 2592-2597. IEEE.
Li, W., Song, Q., Honorio, J., and Lin, G. (2022h). Federated x-armed bandit. arXiv preprint 1526.
Littlestone, N. and Warmuth, M. K. (1994). The weighted majority algorithm. Information and computation, 108(2):212-6611
Liu, C. and Belkin, M. (2018). Accelerating sgd with momentum for over-parameterizee learning. arXiv preprint arXiv: 1810.13395
M Ghari, P. and Shen, Y. (2022). Personalized online federated learning with multiple kernels. Advances in Neural Information Processing Systems, 35:33316-33329.
Ma, S., Bassily, R., and Belkin, M. (2018). The power of interpolation: Understanding the effec- tiveness of sgd in modern over-parametrized learning. In International Conference Machine Learning, pages 3325-3334. PMLR.
Mahdavi, M., Yang, T., and Jin, R. (2013). Stochastic convex optimization with multiple objectives. Advances in neural information processing systems, 26.
McMahan, B., Moore, E., Ramage, D.,, Hampson, S., and y Arcas, (2017). Communication- efficient learning of deep networks from decentralized data. In Artificial intelligence and statistics, pages 1 1282. PMLR.
Mishra, N. and Thakurta, A. (2015). (nearly) optimal differentially private stochastic multi-arm bandits. In Proceedings of the -hirty-First Conference on Uncertainty in Artificial Intelligence, pages 592-601.
Mitra, A., Hassani, H., and Pappas, G. (2021). Online federated learning. 202/ 60th IEEE Conference Decision and Control (CDC), pages 4083-4090. IEEE.
13

---

Park, J., Kwon, D., et al. (2022). Ofedqit: Communication efficnienteinnnnnneeeee online federated learning via quantization and intermittent transmission. arXiv preprint (tth:2225506499//
Patel, K. K., Wang, L., Saha, A., and Srebro, N. (2023). Federated online and bandit convex optimization. In International Conference on Machine Learning, pages 27439-27460. PMLR.
Rakhlin, A., Sridharan, K., and Tewari, A. (2011). Online learning: Stochastic, constrained, and
smoothed adversaries. Advances in neural information processing systems, 24.
Ren, W., Zhou, X., Liu, J., and Shroff, N. B. (2020). Multi-armed bandits with local differential privacy. arXiv preprint arXhv:2007.03121
Sajed, T. and Sheffet, O. (2019). An optimal private stochastic-mab algorithm based on optimal private stopping rule. In International Conference Machine Learning, pages 5579-5588. PMLR.
Shalev-Shwartz, et al. (2012). Online learning and online convex optimization. Foundations and Trends@ in Machine Learning, 4(2):
Shalev-Shee Saalez,,, Shamir, O., Srebro, N., and Sridharan, (2009). Stochastic convex optimization. In COLT, 5.
Shariff, R. and Sheffet, O. (2018). Differentially private contextual linear bandits. Advances in Neural Information Processing Systems, 31.
Sherman, U. and Koren, (2021). Lazy oco: Online convex optimization on switching budget. In Conference on Learning Theory, pages 3972-3988. PMLR.
Shi, C. and Shen, C. (2021). Federated multi-armed bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 9603-9611.
Shi, C.. Shen, C., and Yang. J. (2021). Federated multi-armed bandits with personalization. In International conference on artificial intelligence and statistics, pages 2917-2925. PMLR.
Srebro. N., Sridharan, K., and Tewari, A. (2010). Smoothness, low noise and fast rates. Advances in neural information processing systems, 23.
Steinhardt, J. and Liang, P. (2014). Adaptivity and optimism: An improved exponentiated gradient algorithm. International conference on machine learning. pages 1593-1601. PMLR.
Tao, Y., Wu, Y., Zhao, P., and Wang. D. (2022). Optimal rates of (locally) differentially private heavy- tailed multi-armed bandits. International Conference on Artificial Intelligence and Statistics, pages 1546-1574, PMLR.
Tenenbaum, J., Kaplan, H., Mansour, Y., and Stemmer, U. (2021). Differentially private multi-armed bandits in the shuffle model. Advances in Neural Information Processing Systems, 34:24956- 24967.
Tossou, A. and Dimitrakakis, C. (2016). Algorithms for differentially private multi-armed bandits. In Proceedings of the AAAI Conference on Artificial Intelligence.
Tossou, A., Dimitrakakis, C., and Dubhashi, D. (2017). Thompson sampling for stochastic bandits with graph feedback. In Proceedings of the AAAI Conference on Artificial Intelligence.
Vaswani, S., Bach, F. and Schmidt, M. (2019). Fast and faster convergence of sgd for over- parameterized models and accelerated perceptron. In The 22nd international conference artificial intelligence and statistics, pages 1195-1204. PMLR.
Wang, C.-H., Li, W., Cheng, G., and Lin, G. (2022a). Federated online sparse decision making. arXiv preprint xrXV:22202.13443
Wang. H., Zhao, D., and Wang, H. (2022b). Dynamic global sensitivity for differentially private contextual bandits. In Proceedings of the 16th ACM Conference on Recommender Systems, pages 179-187.
14

---

Wang. H., Zhao. Q. Wu, Q. Chopra, S., Khaitan, A., and Wang, H. (2020). Global and local differential privacy for collaborative bandits. In Proceedings of the 14th ACM Conference on Recommender Systems, pages 150-159.
Wang, Y., Hu, J., Chen, X., and Wang, L. (2019). Distributed bandit learning: Near-optimal regret with efficient communication. arXiv preprint
Wei, C.-Y. and Luo, H. (2018). More adaptive algorithms for adversarial bandits. In Conference On Learning Theory, pages 1291-1291. PMLR.
Woodworth, B. and Srebro, N. (2021). An even more optimal stochastic optimization algorithm: minibatching and interpolation learning. Advances in Neural Information Processing Systems, 34:7333-7345.
Wu, Y., György, A., and Szepesvári, C. (2015). Online learning with gaussian payoft's and side observations. Advances in Neural Information Processing Systems, 28.
Wu, Y., Zhou, X., Tao, Y., and Wang, D. (2023). On private and robust bandits. arXiv preprint arXivv:332..2226.
Yi, J. and Vojnovic, M. (2022). On regret-optimal cooperative nonstochastic multi-armed bandits. arXiv preprini arXiv:2211.771:
Yi, J. and Vojnovic, M. (2023). Doubly adversarial federated bandits. International Conference on Machine Learning, pages 39951-39967. PMLR.
Zheng, K., Cai, T., Huang, W., Li, Z.,, and Wang, L. (2020). Locally differentially private (contextual) bandits learning. Advances Neural Information Processing Systems, 13:00000-1
Zhou, X. and Chowdhury, S. (2023). On differentially private federated linear contextual bandits. arXiv preprint 332.
Zhu, Z., Zhu, J.. Liu, J., and Liu, Y. (2021). Federated bandit: A gossiping approach. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 5(1):1-29.
Zinkevich, M. (2003), Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th international conference on machine learning (ieml-03), pages 928-936.
15

---

A Related Work
Online learning with stochastic adversaries. Online learning with stochastic adversaries has been
extensively studied (Rakhlin et al. 201T, Duchi et al. 2011
Hu et al.
2009
Li et al., 2020a Caron
et al. 2012; [Buccapatnam et al. [0144] 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.] since online learning with stochastic adversaries can be transformed into the stochastic convex optimization problem using online-to- batch conversion. In the federated setting. |Mitra et al. (202T) proposed a federated online mirror descent method. Patel et al. (2023) presented a federated projected online stochastic gradient descent algorithm. Research online learning with stochastic adversaries incorporating DP has also seen significant advancements (Bassily et al., 2014 2019; Feldman et al., 2020 Asi ct al. 202 b 2022b).
Online learning with non-stochastic adversaries. Online learning with non-stochastic ad adversaries has been extensively studied Dessc-Bianchi and Lugosi [006; Littlestone and Warmuth [994] |rrendd and Schapire| 1997; Zinkevich|[20033 Federated online learning with non-stochastic adversaries, a more recent development, was introduced by Hong and Chae (202T). Mitra et al. (2021) developed federated online mirror descent method. |aar et al. (2022) presented a federated online gradient descent algorithm. Kwon et al. (2023) studied data heterogeneity. Furthermore, [L et al. (2018) and Patel et al. (2023) explored distributed online and bandit convex optimization. Gauthier et al. (2023)
focused on the asynchronous settings. Research into online learning with limited switching has also
been explored by Kalai and Vempala (2005); Geulen et al. (2010); Altschuler and Talwar 2018);
Chen et af. 2200)) Sherman and Koren (2021) ): He et al. (2022) et al. (2022b); [Cheng et al. (202))
Differentially private online learning with non-stochastic adversaries was pioneered by Dwork al. (2010). Several studies have explored OPE problem with DP constraints (Jain et al. 2012 Guha Thakurta and Smith, 2013] Jain and Thakurta| 20144] AAgawal 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. [aapann et al. (2023b) focused on online classification problem with joint DP constraints. Fichtenberger et al. (2023) introduced constant improvement. Gonen et al. (2099) 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. SShlee--hwaar ct al.] (2012) studied the weighted majority algorithm. There is also 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 al. 2022a). p. Additionally, some researchers have recently focused on the variance or the path length of the best expert (Cesa-Bianchi
ct 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 20015] Tossou and Dimitrakakis) 2016) Sajed and Sheffet 2019; Azize
and Basu, 2022). Further, Hu and Hegde (2022) proposed a thompson-sampliee -ameling-based ap approach.
Tao al. (2022) explored the heavy-tailed rewards scenario, and Chowdhury and Zhou (002a))
achieved optimal regret in 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 (2020) 2022b) and Hanna et al. (2022). Further- more, Hanna et al. (2022); Chowdhury and Zhou (2022b); Garcelon et al. (2022) and Tenenbaum et al. (222)) focused on the shuffle model. Li et al. (203)) studied kernelized bandits with distributed
biased feedhack. |Wu et al. (2023) and Charisopoulos et al. (2023) tackled privacy and robustness
simultancously.
16

---

Federated multi-armed bandits. Federated bandits have been studied extensively recently. Shi and Shen (202T) and Shi et al. (202I) investigated federated stochastic
bandits without and with personalization, respectively. Wang et al. (2019) considered the distributed setting. Huang al. (202T), J. Wang et al. (2022a) and and Wang 2022) studied federated linear contextual bandits. Li et al. (2022b) focused on federated X' R'-armed bandits problem. Additionally, (eea--Ceaann Bianchi et al. (2016), Bar- Ont and Mansour 2019). Yi and Vojnovic (2022) and Yi and Vojnovic (2023) have studied cooperative multi-armed bandits problem with data exchange among neighbors. M Ghari and Shen (2022) have explored online model selection where each client learns a kernel-based model, utilizing the specific characteristics of kernel functions.
When data privacy is explicitly considered. [L et al. (2020b) and Zhu et al. (2021) studied federated bandits with DP guarantee. Dubey and Pentland (2022) investigated private and byzantine-pree cooperative Decision-making in the bandits setting. Dubey and Pentland (2020) and /Zhou and Chowdhury (2023) considered the linear contextual bandit model with joint DP guarantee. [.i et al. (2022a) studied private distributed linear bandits with partial feedback. [Huang et al. (2023) studied federated linear contextual bandits with user-level DP guarantee.
B Applications of Differentially Private Federated OPE
Differentillly private federated online prediction has many important real-world applications. We provide three examples below.
Consider 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 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.
Personalized Healthcare:
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 's role is to collect 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.
updates from these clients to improve the global
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-pres pereccypreseriinggg 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.
C Algorithms and Proofs for Fed-DP-OPE-Stoch
C.1 DP-FW
In DA--DOPPE--toch. we run DP-FW subroutine (Asi et al. 2021b) at each client i in each phase p. DP-FW maintains Tj binary trees indexed by S j S Ti. each with depth j. where Ti is predetermined parameter. An example of the tree structure is shown below. We introduce the notation s E (0. 1 to denote vertices within binary tree j. @ signifies the tree's root. For any 8, s (0, 1} $$ if s'0, then s denotes the left child of s'. Conversely, when s s'1, is attributed as the right child of s'. For each client i, each vertex in the binary tree j corresponds to a parameter ii.j.s and gradient estimate Vi.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 left child vertex 8, the algorithm maintains the parameter Ji. and the gradient estimate v. identical to those of its parent vertex s', i.e. Vi.j. Ui and Ti.j. Lijj.'' As it proceeds to a right child vertex, we uniformly select 2 1 loss functions from set B.,p {4.2- ....., ......,.2. 1 to subset Bij.s without replacement, where denoting the predetermined batch size and |s| representing the depth of the vertex s. Then the algorithm improves the gradient estimate Ui at the current vertex s of tree j using the estimate ji at the parent vertex s', iee
Vigi Uiij, Vi(zaj Big,e) Vi( (B...,))
(3)
17

---

4n2" Algorithm 3 DP-FW at client (Asi et al. 2021b)
1: Input: Sample set B, number of trees Ti, batch size b.
2: for =1 to Ti do
3: Set v4.... = -
4: Uniformly select samples to Bi.
5: Vij.0 = (z (.0)))
6: for DFS do
7:
Let 8 = s' where {0, 1)
8:
a then
9:
Ui ji Lij. Di.j.s
else
11:
Uniformly select 2 2-1+ samples to B Update vij.s according to Equation 13: end if
14:
end for
15:
end for
16:
Return (ougsabeee)).........
where Vi(:; (i,.s) [ie.
EieB.,. vi(.), and B.y.a is the subset of loss functions at vertex in the binary tree for client The full algorithm is shown in Algorithm
00
10
11
Figure 3: Binary tree with depth j = 2 in Algorithm
C.2 Proof of Theorem and Corollary ( pure DP)
Theorem 5 (Restatement of Theorem
D. Assume that loss function 1,,(+) is convex, o-Lipschitz, 8-
smooth w.r.t 11- Setting >i.j.
4022 h
25-1 1-- and Ti log beff.
Fed--DP-OPE-Stcch
be
aood
(i) satisfies s-DP and (ii) achieves the per-client regret of
o (a (a+ log
Tlogd
vaB log d T log m /
m
with (ili) communication cost of O (mid// aloo d
Te8
We define population loss Lx(x)= E m En (.((0)))) The per-client regret can be expressed as
We use kkp.kk W.pp Fi,p, and k to denote quantities corresponding to phase p. iteration k, and client i. Also we introduce some average quantities 0p.k Σm= p. and Wp,k m Σ Wi.p.k
ΣT L.(1,.) F ΣT Lo(x*)
To prove the theorem, we start with Lemmal that gives pure privacy guarantees.
Lemma 1. Assume that 2T) < b. Setting \ij he Fed-DP-OPE-Stoch c-DP.
Proof. Let and S' be two neighboring datasets and assume that they differ in sample 4,,4, or K,,,, where 21 < t 2P, Let B be the set that contains 4 or 4. Recall that
[Bi 2-1bb The key point is that this set is used in the calculation of Uk & for at most 2/-1s|
18

---

iterates, i.e. the leaves that are descendants of the vertex. Let ko and 11 be the first and last iterate such that Bi is used for the calculation of V/s pi, hence ky Kig + 20-1a1
First, we show that ((Gn, U1,1,1,..... (Cn, p.,), (e.0) ((en, "1,1,),---- (Cn, p,)) holds for I S n S d. For our purpose, it suffices to establish that ((en, ko.... (Co, .1.) (e.00 (Cen, Ao).p.. (Cn, 5% p...p..k,) holds for I n $ d, since l,,s or 1 11.0, is only used in client i1, at phase P1 and iteration ko..... 11- Therefore it is enough to show that (Cas U6 .e) ( (1-)0
(Ca, o (1..i.)) holds for ko I k S 11 and I n S d, because k1 - ko + S 2 Note
2-1-11- Setting Ae., = 4a2' and applying standard results of Laplace mechanism (Dwork et al. (2014) lead to our intended results. Finally, we can show that (W,,,,,,,...
that (Cn, Vi..PI.k - &))l I
4a
be
P.K.k ".,
(e,0) (11,1,K s P.K) by post-processing.
To help prove the upper bound of the regret, we introduce some lemmas first. Let be the tine-step, p be the index of phases, i be the index of the clients, and (i.s) s) be vertex. For every index 1 S k S d of the vectors, we have
Lemma 2.
(O(1)e + )
E Eexpp {c(Up.j...
cxp (LLA(Eaps)))) cxp
bm
where Upj.s Ei= Vi.....-
Proof. Let us fix p. f, l and i for simplicity and let AJ.o = Up..s.k - VLL.( We prove the lemma by induction the depth of the vertex, i.e., |s]. [s] O, then Us... Vi B....)) where p..0 0 is sample set of size b. Therefore we have
SlexpeAj.. = Elexp cl P...
Vha (Tt.p.))
E
expe
Σ
(lu(iiphh0is) - VLe, (Fimp.i))
mb
F=1
II
E
exp c
(Vla(Ti (Leu(Tipp.)))
bm
a. vE(m)
cea2'
S exp
2bm
where the last inequality holds because for random variable X [-a,a], we have c²aa'
Elexpe(X - -[X]] exp
Assume the depth of the vertex |s| 2 0 and let s = s'a where E (0, If a = 0, clearly the lemma holds. If recall that v. Uip + Vi(xiipiss Binsss)) VI(Iipj. Bi....e), then
Aj.a Ep.jack (LLu(rippss))
m
1
Aj.s'
Vla Vlaliinni Bip..ss
Vl (Tipsis Bi.p..s)
m
(FLpp + (Le..
Let B.n.(.s)) U( ( Bipre be the set containing all the samples used up to vertex (j s)
in phase at client i. We have
E (expcAj..
= E exp
c(Aj.a' +
Vla (Zippiii (B.ppps:::
Vla (Fipsioi Bi...i)))
exp
Vee + V
1 m
m
exp
c(Ajss' + m
Via B Bipaa)
Vly (ai Bip...s))
m
19

---

VLLA(Diph))) + (LL (Bioecti)))
B exp (cAj,a') (Bpp)())))
1 Vlu (lu Bispaia)
Elexp
c
Vlelripast Bipis)
i=1
(Exx(E + VL ( ((.
Since (1,((1))) is B-smooth w.r.t. II, have
Vl (Zippiii p.p.e) Vla (asppii Bipd S B1| Iappoiel
Since vertex (j,s) is the right son of vertex (j, 8'), the number of updates between Tipp.j. and Tip.i is most the number of leafs visited between these two vertices i... 2/-1a1, Therefore we have
|
Ti.pois |l S M.pp. T - 22-1e1
2/
By using similar arguments to the case [s| O, we can get
E
exp
cl m
(4 Bips..) m
Vle Bepsii))
V (Liippiip + (LL.(TTaps.r)) Binrebio)
x exp
((1))2332-211) 2/1
exp
ml miliipp.iel
((1)628822-1
S exp
bm
Then we get Applying this inductively, we have for every index 1 k d
(01))2 |s|
Elexp S Elexp eAg, exp exxp
bm
((1)c + 32)
S exp
bm
Lemma 3 upper bounds the variance the average gradient.
Lemma 3. At phase p. each vertex (j, s) and 2--1 S < we have
(V d bm
T Upj.s VTn(Er.p))))) S (a B)0
where Up...
1 m Em Vip.....
Proof. Lemma implies that Ep..... VLe (Zi.p.)) is O (asss--uuuuusssss Gaussian for every index 1 < < d of the vectors. Applying standard results of the maximum of d sub-Gaussian random variables, get
a +
Blllep.j. (Lo(Fup.je))la)) 50 (
(
32 bm
v log d.
20

---

Lemma gives the tail bound of the sum of i.i.d. random variables following Laplace distribution. Lemma 4. Let Sin be IID random variables following the distribution Lap( (.)))) Then have
E
max
Σ
Sim
OlVmds.ss In
misnsd
1=1
Proof. Si,n's are md IID random variables following the distribution Lap(As.j.)) We note that
1
1
E [exp(uE).)]
A1.jee uu2 [u] S
Aijis
Since 1-Aa.p,auu u I 1 2,, u2² I exp(2Xr.5,s ²u²), when |u| S 2A.,J.a Es, sub-exponential
with parameter (4) 2.....). Applying standard results of linear combination of sub-exponential conclude that Ei= Er.., denoted as Y,, is sub cub-exponential with parameter (Amr)... 2A).j.)). From standard results of tail bounds of sub-exponential random variables, have
random variables,
(- Sm.d.
c²
((Y)) 2 c) 2exp
if0 S c 2m
P(YY 2 Sexp
if 2mAijs.
Since
max Y 2 Emisnga P([Va] c), m::Snnd
we have
c²
P( max m:Innd
|ul 2 c) S 2dexp "'mmi...
if0 S c 2mnii...
P max |nl 2 c) S 2dexp (-4Mese) ml Sana
if 2 2mA
Then we have
000
E
max
Ynl
P
max
Y
20 de 2mdiis
Snsd
J0
nilEnsd
-V8 In dhi.jo +
max Y |2l 2 de m:1Sndd
Vsm In deiisit
P
max milsaa
Yul 20 de
2mddisaa
e² de Smddig.
v 88m In Ind
+
2 exx
Ind
2cxp Ind
c
de
Dhiso
toc
V8m In + V8mdigg
exp (-u²) du
+8hij (
exp(-u)du
22/m-Ind
+oc
V8mmlnd + V8mdijje exp (-u²) du
8hrji In 8d1 exp(-u)du
W8mlndde..a + VSMTdigs + Sh dddd + 8
OOVmdas. Ind).
21

---

Lemma 5. Setting Ai.j,
4023
we have
a2 In d bs m
E (Tp wp.k)l
min mEx pp kr w) + +0
Proof. Since pp = arg mnine..snnns we denote wp.k as Cp2* and we have
th Ei=1 (fens Pippa) + Sin)], where Ei, ~ Lap(As.se)
k.p Up.k) = (Cnu, Tp.k)
min miSnnd
(cn, Up.e +
Si,m
Sim
i=
i=1
m
min n:l Smidd
(Cas Tp.k) +
max m: Innsd Sid
Es,n
min
Si.
772 mil
Snnddd
m S1.
min (Cas (p,k) + max aiIgndd
Σ
m7 Snnd
Applying Lemma 4 we get
Ae.j. In Vm
E k. Uf pp S EE
min (0 pp w) +
With the lemmas above, we are ready to prove Theorem
I
Proof. Lemma implies the claim about privacy. We proceed to prove the regret upper bound.
(. + (V LL Dippht1 Tipit) + kt xipp,
(6)
$ Le( pipp. (VL, (Zi.p.)) up Zippi) 3tipp,
(L(np)))) + n. (V L1 (zt x² -iipk) + M.p.k (V (ZL.(eep.k)) Up up x²)
+ T.pk (Tp,ks Pp x²) + 31ippkk?
[x( + m.p.k [T(=**) (-=))))- T (x(p.))) Wip. V Tp loo + (U Wp.k) (9)
min (ūp.k w)) 3T..p..
where (a) is due to 3-smoothness, (b) is because of the updating rule of ri,p, and (c) follows from the convexity of the loss function and Hölder's inequality.
Subtracting L+ (a*) from each side and taking expectations, we have
([Le(Dip)411) [x(x)) S (1 ki.p. [E (Fip..)) L2 [x(xx)) + np.p. E/IVLL (xipp.)) 1oo
+ Th & wp.k) min (Tn w)] + BT..p.k. 2
Applying Lemma 5add Lemma
3 we have
(V
(Tog log bm
pk.p. (TT [x(x')) + 1a (300
Ind
+
be
mm
22

---

Let og "..p, 3)0
log d bm
a2
0
lud vm
+
2/2 3.
We simplify the notion of
br
p.p. to Then we have
K
K
E (2(.pp))) - Lx(x)) ]| 5
(1 mp)
k' k'=1
<>
(k: + 1)1:
04
K(K - 1)
k
(A: + 1)2
ON (K - 1)2
k=1
where 7/k E+I
2
Since K = 2 simply algebra implies that
log d
a2 Ind
B 2
E[L((Fip,)) (,(x)) (a (a+
bm
bs b
At iteration 2P-1 St 2", setting b
1p-1jø and Ti log
20-1
beBym alog d'
in Equation (4)
we have
Pv a log d log d
((L(( 5 (a
+
2
m v 2
Therefore, the total regret from time step 2 to 20+1
1 is at most
2
2
Te(ri,)) min
Σ Tu(u)
50 (a (a+ B)p
2a log d
pVaB log d m V
dEA 2=
2P
Summing over p, we can get
T
T
log T
22 log
+ pVa3 log d/20
L (1(
min uEX
Σ
(u)
Σ p=l
0
(a+ B)p
m VE
log
2D log d
VaBlog log d m Ve
log T
0
(a + 3)
PV
Pv PV2F
m
p=1
p=1
s 0
(a + B3 log T
Tlog d
VaBlog d d
m /
Now we turn our focus to communication cost. Since there are log phases, and within each phase, there are O(27i) leaf vertices where communication is initiated, the communication frequency scales in O,,, 21). Therefore, the communication cost scales in ( log d)).
Corollary (Restatement of Corollary 1. If = 0 log d E-DP and (ii) achieves the per-client regret of
Vmlle then, Fed-DP-OPE-Stoch (i) satisfies
Reg(T, m) =0(1
Tlog
log T log d vmn
m
with (iii) communication cost of O (md T).
23

---

Proof. Similar to the proof of Theorem 1 we can show that
log d
a2 Ind
([ [,(x)) s (a+ (3
(5)
bm
be beymm
2
At iteration 20-1 St < 2p, setting b 20-1 and Ti 1 in Equation
have
log d
aln
B (<(pp))))))) - 50 (a V
2 + 2
+ B
Since 01
log VmTT have
log
2Pm + a alnd d 2
(L Le(x*)] S (a (a+ s/
Therefore, the total regret from time step 2 to 2 is at most
2
2-+1-1
s0(1
2D log d
log d v /m
Σ
min wEA
Σ Le(u)
m
2=
t
Summing over p, we can get
log T
2 log d
a log d vms
La (x(
min ueA
Le(u)
0
m
log T
2a log d m
log d T mm
o
T log d
log d log T
m
Vme
The proof of the DP guarantee and communication costs follows from the proof of Theorem
C.3 Theorem 6 (for approximate DP)
Theorem 6. Let 8 1/T. Assume that loss function 1,,(+) is convex, a-Lipschitz, 8-smooth w.r.f. 27-1
||- 1/2. Assume 5 (ar l2 1/8) log 2/2/4 vp-I Setting As,j,e /22T//2 log(2" 188 b (p-1)z+ and
892--1774
mm T. = 3/ log l20g(22-111 (0)) log
Fed-DP-OPE-SS is (e, (), the communication cost scales in
O (md2Ti log T') and the per-client regret is upper bounded by
o ((a (a (a+ B) T
Tlogd
22/331/3 log 2/3 (d) log 2/3 (1/8)T /2lgg))///11////// (3(
m 2/3
m
Proof. We apply the following lemma to prove privacy in this setting.
Lemma Asi et al. 17 1o 2021b), Lemma 4.4). Let 2 2 8 1/T and < 2 log(1/0), Setting
Xi.i
(8) we have Fed-DP-OPE is DD)
bc
Theorem 6 then follows using similar arguments to the proof of Theorem |
24

---

end for C.4 Extension to Central DP setting
In this section, we extend our Bed-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 global privatization process on the server side. Specifically, in Line g when communi- cation is triggered, each client sends ((Cn: ] ne[d] the server, where cl,-.-o Cd represents d
vertices of decision set X' Aa. In Line 5) after receiving {(on Vt.j.s) heeed from all clients, the central server privately predicts new expert:
1 m
m Σ
3, arg min c Endd
Cns U.j.s)
Sn
(6)
where C.. Lap(usaa) and Pj.s
4 Ums
Other components remain the same.
Algorithm 4 Fed-D--OPEE-toch (CDP): Client
Input: Phases P, trees Ti, decision
Ag with vertices (cI...., cal, batch size b.
2: Initialize: Set 2;,1 = 2 E X' and pay cost 4,1 (21,1).
3: for p
do
4: Set B. 24,20-2,-- 24...-2,....,4 14,20-1-1111
5: Set k and ri.p,1 = Fi.p-1.K 1.K
6: [Mr.j.s ).e = DP-FW (Bi.p. Ti,b)
7:
for all leaf vertices reached in DP-FW
8:
Communicate to server: {(ons Ut.j,) heed
9:
Receive from server: Wje
10:
Update Tipp according to Equation
11:
Update k
12:
end for
13:
Final iterate outputs Ti.p.K
for 2p-1 to 2 do
15: Receive loss 4.t X' - I2 and pay cost (1..p)
16: end for
17:
Algorithm Fed-DP-OPPE-Stou (CDP): Central server
1: Input: Phases P, number clients m, decision set X = Aa with vertices (ci...., cat.
2: Initialize: Pick any z X' and broadeast to clients.
3: for 2 to P do
4: Receive from clients: {(en ( InE(d]
5: T. arg argmin min
cnd1 m EE (cn, v..j,)) Sn.
6: Communicate clients: W.js
7: end for
Now we present the theoretical guarantees in this setting.
Theorem 7. Assume that loss function (.,(()) is convex, a- a-piscchitz 8-smooth w.t.. || 1l1. Fed-DP. OPE-Stoch (i) satisfies =- e-DP and (ii) achieves the per-client regret of
T Togg m
+ loBlog d d Tog
Vmve
with (ii) communication cost of
( d
TeB log
To prove the theorem, we start with Lemma 7 that gives pure privacy guarantees.
Lemma 7. Assume that 2T. < b. Setting Hj
1a2/
Fed-DP-OPE-Stoel is E-DP. biee
25

---

Proof. Let S and S' be two neighboring datasets and assume that they differ in sample 4,, or
Kn where 2P I 4 < 2P: The algorithm is 8-DP we have (I1.1KK,--- Fmm..KK (e,0) (L,,,,K...,, P.K).
Let di be the set that contains 4, 4..5 Recall that J.sl = 2 The key point is that this set used in the calculation of Us &e for at most 2/-1= iterates, i.e. the leaves that are descendants of the vertex. Let kg and 11 be the first and last iterate such that B is used for the calculation of UA .p Ks hence b ko + s 20-1a), For sequence 0;, ................................ aj. use the shorthand as: = {a.....,.)) aj)-
Step I: X1. kn (e,0) Xim,p1 ku:k; and Wp. kotks (e,0) W ko by basic composition, and report noisy max
We will show that pa.... pm. and (1 (x1.p1,,o" Aot ........ oy m. are e-indistinguishable Since
Bigg. used to calculate Pi..i.k for at most 2 [s] iterates, i.c. k - Ko + < 2/-1s|, to show that & (z--1710) W pr for ho S k hn and then apply basic composition and post- processing. Note that for every kn S S ki, the sensitivity ((ens Vir.PI. V. S
|-| it is enough
4a 196
therefore, 1 Ei= (Cns vs.p).)) Eis (Cn; k. I 2-1-1m6 Using privacy guarantees of report noisy max (Lemma we have Wp (5)-m)) 0) wpy for ko S h S by with ul, bmz
4a2'
Step 2: X1.m (e,0) I.P.I by post-processing
In order to show (,1,,, P.K,,K) (c.0)) (I "m. we only need to prove that K...,, Fmmpr. R) (s,0) KK.......... In kmp.k) and apply post-processing. It is enough to show that iterates (.................. (.m.p.))
k) and (11..,........ " <m.pp.)) e-indistinguishabl..
The iterates 21:m.p1.110-1 and o Limmpi, 1:ko-1 do not depend on ligh or Kn hence 0- indistinguishable. Moreover, given that hot. Im.p and (oi .... m.pp e-indistinguishable, it is clear that (I1,p) (1 tl km)...) and (r' (m ... pmp. K) are indistinguishable by post-processing.
m.p . are
To help prove the upper bound of the regret, introduce some lemmas first.
Lemma 8. Setting Pj.s
4x22 mbe
we have
min (ūp,:: w) + O (22) In d mbe
E (T mp.k)) S E
wEX
Proof. Since Wp.k = arg : note p..k Cn. and we have
1 Em (Cni Uepat) + Snl, where Sn ~ Lap(Hg,,), we de-
(Wppee (p.k) = (Cnr, (p.k)
min ((eny (p,k) (n) Sa.
miSngd
min (Cn, Upok) ) + max |Sal- m:1nndd
m:15nd
Standard results for the expectation of maximum of d i.i.d. Laplace random variables imply that
E
max
|Sml
< OpH,, In d). Therefore,
melSnne
(ū Up.h)l s
(pp. w)) + +0 (13.e wEX
min
Then ready to prove Theorem
26

---

Proof. Lemma 7 implies the claim about privacy. Following the same arguments in the proof of Theorem we can get
(IL((11,,841) - (xxx)] S (1 Ti. ,x (Fepp.) - [x(xx)) + p. LI (T.. Boool
+ +.,p,.k (ūp,k: mp.h) min (Jp.ks w)] + pnppp...
weX
Applying Lemma and Lemma 3 we have
B ((Ip(rip)+1)) -+(x==)))) & (1 ph.p. ) IE - [x(xx*)] (a (a (V bm
logd
In
1
+
+ 2 +28m ST..p.k
be
(V
Let = Ti.p.k + 8)0
log
+
n.p.a bc
0
[ud]
+ BT.pp. We simplify the notion of
bm
p. 77.- Then we have
K
K K-1
E
Te (Fip..) - [x(xx')
5 2
O
II i>
(1 me)
k==1
K
(k+ 1)k K(K 1)
OA
K
(I: 1) (K - 1)2
where 1/ E+I
2
Since K 2 simply algebra implies that
log d bm
a2 Ind
B 27:
[[(((app.) - T,(xx)) s (a (a+B))
+
bem
At iteration 2p-1 st < 2", setting b = 1リ- and Ti log
20-1
be a log
we have
log d
aB log d v /mv22 2
| (TT,p)) [x(x")] 0 (a (a+ + B)n
2m
Summing over all the timesteps, we have
El(u) <
Tlog d
aa log d. d Vm
(x..)) min D Proof of Lower Bounds
(3
Bog
+
Nex
The proof of communication cost similar to that in proof of Theorem
Theorem 8 (Restatement of Theorem 2. For any federated OPE algorithm against oblivious adver- saries, the per-client regret is lower bounded by S0 log d). Let (0, and 5 o(1/T), for any logd T)).
(e, federated OPE algorithm, the per-client regret is lower bounded by 52 (min
Proof. Consider the case when all clients receive the same loss function from the oblivious adversary at each time step, i.c. 4, K. Then define the average policy among all clients (k()
m (k), Vk E [d]. Now the regret is
m
T
m
T
m
T
kalx*)
((()))))
- Σ M(x*)
m
m
27

---

I
((o(k) (((K)) - - (1(x))
1=1
Pt)((k) .1((K) - Σ (1x))
t=1
T
(k(k) ((())
' (((a))
Note that (k) is defined by Pı,:(k), ...,),.................. (k)(k), which in turn are determined by 4.1,..... mm.1-1 According to our choice of 4,, k4 p)(K) is determined by ......... Therefore p1, 1/2 Pt are generated by a legitimate algorithm for online learning with expert advice problems.
There exists a sequence of losses 11 ..,,....4. 11 such that for any algorithm for online learning with expert advice problem, the expected regret satisfies (Cesa- (Cesa-Bianchi and Lugosi (2066), Theorem 3.7)
T
T Σ ((a²)) 2 2R(VTlogie 1=1
PL(K)
1=11
R=1
Therefore, we have
E
(2
4,(x*)) 2 (VVTT(lol)))
m
From Lemma 9 if (0 and 6 = o(1/T). then there exists sequence of losses 1 12 .......... such that for any (e, 5)-DP algorithm for online learning with expert advice problem against oblivious adversaries, the expected regret satisfies
T Σ E4(=')=
min log d T :1)
Σ p
2 Ω
E
Therefore, have for any (e, algorithm,
T
m
log d min
E
4.(()))))
4x(x*)) 2
s (T)
m
Lemma 9. Let E (0, and 5 = o(1/T) There exists sequence of losses l l,.... by such that for any (c, ()PD) algorithm A DP-OPE against oblivious adversaries satisfies
Σ 1(xx)) 2 Ω min llog d -T))
Σ (((x))
min x" E(d
Proof. Let n. E N. Define E )" containing records, where {0. 1)d. The function 1-Selecty: ) + [d] corresponds to selecting a coordinate b [d] in the batch model.
Then we define the regret of 1-Select,. For batched algorithm M with input dataset and output b E (d], define
T2
(n(a*)) )
Regi-seles (M(y))
n Σ vi( min eld
Σ
Let A be an (c, DDDD algorithm (10,1)a)7 T (ld)² for DP-OPE against oblivious adversaries
with regret ΣT (((x)) mingreld ΣT= 4xxx)) ) < a. Setting T n. can A to construct
28

---

an (s,6)-DP algorithm M for 1-Selecty in the batch model. The details of the algorithm appear in Algorithm
Algorithm 6 Batch algorithm M for 1-Select (Jain et al. (2023). Algorithm with = 1)
1: Input:
(y1,....31) Un) E )" where {0, 134, and black-box access a DP-OPE algorithm A for oblivious adversaries.
2: Construct a stream < y with n records.
3: for = 1 to n do
4: Send the record 25 to A and get the corresponding output Zt.
5: end for
6: Output b Zn-
Let > a E RR,, and T,d, E N, where T = I DP-OPE algorithm A: (10, 1342 ((d)² for oblivious adversaries (E, DP and the regret upper bounded by a, i.c Σ 4(x)) min Ei= 4xxx)=====)))))> a, then by Lemma 10 we have the batch algorithm M for 1-Selecta is (e, 6DD and Relea,
Select, (M) z n.
If 5 = o(1/T), then n = Ω log (Lemma
We have a min (1 (0(())) log n =
min ( logd T) So 2 Ω min logd .)) Therefore, if an algorithm for DP-OPE against
oblivious adversaries is (e, diffferrentill private and Σ (e(x)) min Ei=4((0)) 4=x" S a holds, then a 2 Ω (min logd e (e)rr)) This means that there exists a sequence of loss functions h....,y such that El= 4(x1)) - min e(d] E(=)4(x)) 2 Ω min logd .T))
Lemma 10. Let M be the batch algorithm for 1-Selecta- For all 0,8 2 0, E R+, and T, T,d,n E N. where T = n, if DP-OPE algorithm A: (40,1)d) 7 ([d)² for oblivious adversaries is (e, diffeeerentill private and the regret is upper bounded by a, i.e. ET 4(x)) eid Σt= l((x)) a. then batch algorithm M for 1-Selecta is (s, differentially private and Reg (M) <
Proof. DP guarantee: Fix neighboring datasets y and y' that are inputs to algorithm M. According
to the algorithm design for 1-Selecta, we stream y and y' to a DP-OPE algorithm A. Since A is (e, DDP, and M only post-processes the outputs received from A, therefore M is (e, d)-P.
Fix dataset y. Note that if a 2 n, the accuracy guarantee for M is vacuous. Now assume < Let y be the regret of M, that is,
Regret upper bound:
? Regi-Select, Select, (M)
Σ v1(x*) ]
Σ vi(b)
min x e(dd
where is the output of M. The main observation in the regret analysis is that if ar is small, so is Specifically, the regret of M most g. Therefore, 7 < C.
Lemma 11 Jain et al. 2023 Lemma 4.2). For all d, Ne (0, o(1/n), [o, m and (c, 8) 1- Selecta algorithms M: (f0, 17a)a + [d] with Regi, (M) $ 7 we have n Ω log
29

---

E
Algorithms and Proofs for Fed-SVT
E.1 Proof of Theorem 3
Theorem 9 (Restatement of Theorem 3 Let S and ó S. e/d. For any (5,8)-DP federated OPE algorithm against oblivious adversaries in the realizable setting, the per-client regret is lower log(d)
bounded by 22
m2
Proof. introduce two prototype loss functions first: let (x) = 0 for all x E [d] and for j E [d] let 16 be the function that has (x:) 0 for and otherwise 1 (x) 1. Then we define d loss sequences 8 (H......, 1/ such that
10 1= -
11 =
else;
where k
logd and j E [d]- 2ma
The oblivious adversary picks one of the d sequences S S!,....,S! dom. Assume towards contradiction that E E Ele 4.((5,,)))) Σ Et 4a(x*)) s
St uniformly at ran-
log(d)
This implies that there exists d/2 sequences such that the expected regret satisfies ((())) - Ei
Assume without loss of generality these sequences are St ,...... S4/2, Let B, be the set outputs that has low regret on S that is,
-
log(d)
16:
T- k+1
log(d)
Bj (#1. (21,1,..,, km,
[d]"
e (Ii,))
85
t=1
Note that Bj 0 By since if F1:m,1:7 E B3 then among the mk outputs 1-m, least
3mmk (lgg(d) of them must be equal to j. Now Markov inequality implies that 88
P (A E B,) 1/2.
Moreover, group privacy gives
IP (A(S*) E B,) e-mkep (A (A(s)) BBy,) -nkō
1
log d
2vd
2s
4vd
where the last inequality is due to 8 < e/d. Overall we get that
d/2 1
P (A
$ B2) <
4vd
which is a contradiction for 2 32.
E.2 Algorithm Design of Fed-SVT
Fed-SVT contains client-side subroutine (Algorithm ( and server-side subroutine (Algorithm g)
E.3 Proof of Theorem 4
Theorem 10 (Restatement of Theorem 4p. Let 4, E [0, 1]d be chosen by an oblivious ad-
versary under near-realizability assumption. Set p < 1/2, O(log(d/p))
mL* + [log(2T3/(N22))) 4/n, and n e/2n. Then the algorithm is e- e-DP, the commmication cost
30

---

Algorithm 7 Fed-SVT: Client
1: Input: Number of Iterations
2: Initialize: Set current expert æp Unif[d].
3: for = 1 to 7 do
4: if n.N for some integer
then
5: Communicate to server: Σ =V=I-N 1 (z)
6: Receive from server: Ie
else
8: Set It-1
9:
end if
10: Each client receives local loss lif [d] - [0, 1] and pays cost (122)
11: end for
Algorithm 8 Fed-SVT: Central server
1: Input: Number of Iterations T. number of clients m, optimal loss LT, switching budget sampling parameter 7 > 0, threshold parameter L, failure probability p. privacy parameters 8
2: Initialize: Set & = O, т = 0 and = L + Lap (3)
3: while not not reaching the time horizon T do
4: if == n.N for some integer n 2 then
5: Receive from clients: _ (x)))
6: if < x. then
7:
Server defines new query 9: = Em Ere, (o((v))
8:
Let 7/2 = Lap (
9:
if q: + 7/ L then
10:
Communicate to clients: It-1
else
Sample 2, with scores (x()) max m Ex=1 l (xx), (xe)) for x [d]:
P(r: = x) (/)
13:
Communicate to clients: Ft
14:
Set k = k: T, and L L Lap (1)
15:
end
16:
else
17:
Server broadcasts 2, = It-1 to all the clients
18:
end if
19:
end if
20:
end while
scales in (mnTT/N (N), and with probubility at least - O(p), the pre-client regret upper bounded by log" (d) +lon 72 R2, ma
loR(
+ (N I=) log (t) (+))
Moreover, setting = E/ K log(1/0), we have the algorithm is (E, D)-P, the communication cost scales in O (m)TT/N), and with probability at least O(p,, the pre-client regret upper bounded by O
log (d) /log( +log N=.)) (og()))
+ (N + log
Proof. DP guarantee: There are k applications of exponential mechanism with privacy parameter n. Moreover, sparse vector technique is applied over each sample once. hence the applications of sparse-vector e/2-DP. Overall, the algorithm is (e/2 Rn)-DP and (e/2 /2n enn("") 1), DDP (Lemmal 14). Setting e/2w results e-DP and rj = e/ / log(1/8 results in (e.8)-DP.
31

---

Communication cost: The number of communication between the central server and clients scales in (mmT/N). Moreover, within each communication, the number of scalars exchanged scales in O(d). Therefore the communication cost is (mmdT/N)
Regret upper bound: We define potential phase [T/N]:
On
Σ mE(d]
nbn(2//2
where (x) max E T Eper li (z),mL))) Note that do = de 12 and on 2
e e-pptt/2 /2 for all n E [T/N] since there is x E [d] such that Σx= ΣT= lx((x) I mL We split the iterates to [log d rounds NgN, N,,, ..... N2-N where np the largest [T/N] such that Onp 2 00 Let Zp be the number of switches in N, (Mp+1 - N)N] (number of times the exponential mechanism is used to pick 21). Let Z Σ Zp be the total number of switches. Note that Z < 3s + 2p=0 max (Zp- 3, 0) and Lemma 12 implies max (Zp 3, 0) is upper bounded by geometric random variable with success probability 1/3. Therefore, using concentration of geometric random variables (Lemma] 13), we get that
P(Z 2 3s + (4log(1/p) S.
Since K 2 3s + 24log(1/p), the algorithm does not reach the switching budget with probability 1 (p)( So the total number of switching scales as O(logd// (d/p(dd)))) p)). Now we analyze the regret. Define TIN... N as the switching time steps with TcN = T, where C = O(log(// d)).. Lemma 16 implies that with probability at least
P.
T M
T&N
Σ
Σ
Σ
ko(x),)
f=1
t= Tc N+Li=l
T-N-N
m
T.N
122
Σ
Σ
(x),))
Σ
Σ
4. (I+)
N+1
T N+1 i=1
L 8log (()2)))
+ ...)
o=1
mL. + 16log(2T (N) + 4/n 4//++m) f//++mN))
Σ
a=1
(LL' log(d/p) + log(T2/(N2) log(d/p)
4 4log(d/p)
0
+ mN log(d/p)
(8)
Case 1: Setting 17 8/2k in Equation (8) we have
T
ha(0aa)) S 0 mL log d + log² + log(T2/(N2p)) log(d/p) + mnN (odg(g(//))
Case 2: Setting E/ 1..V/lllogg klog(1/8) in Equation 8 we have
T
(x11)) 50 mL ImL*logd' 3/2 d log 1/8) ((NT))/((2p))))))))))))))))))))) log(d/p) + mN log(d/p)
t=1
Lemma 12. Fix 0 <pss s 1. Then for any 1 < k < T/N, holds that
P P(z A + < (2/3) k+2 < (
32

---

Proof. Let N I n.V I M be a time-step when a switch happens (exponential mecha- nism is used to pick Z²). Note that Pnp+1 2 0n We prove that the probability that x, is switched between n.V and Rp+1-V is most 2/3. To this end, note that if a is switched before
1p+1- N then Σ 2P=nN (x(()))) 2 L (log(27)/
therefore Lnges (2) Ln(x) 2
Blog(2T /(N2 p)) 4/17 Thus we have that
P (Iy is switched before N)+1N) v
=x) (Lmp)(())) Ln(x) 2 4/m)
=
=E|d]
[Lmp11 - Lu (x) 2 4/n} (1)(11
On
sE|d
1- 1- (bmppp (t) 1x)
On
1 1-e-2
#E|d]
$ 4/3 (1
pnpti/@n)
S 2/3.
where the second inequality follows the fact that 1a 2 b) S 1-ee for a, b, 17 2 O, and the last
I----s
inequality since 2n,-1/ Ón 2 1/2. This argument shows that after the first switch inside the range N,,,, up+t 1]. each additional switch happens with probability at most 2/3. we have
P ((zp k + s (2/3) (1/3)).
Lemma (Asi et al. (2023), Lemma A.2). Let WI.... Wn, be i...d. geometric random variables with success probability p. Let W >i= W. Then for any k 2
P(W > 2k/p) S exp(-k/44
F Experimental Supplementary
The simulations were conducted on 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 b
G Experiments on MovieLens-IM
We use the MovieLens- IM dataset (Harper and Konstan 2015) to evaluate the performances of Fed- SVT, comparing it with the rating matrix of 6040 users to 18 movie genres (experts) R [e.gl E
model Sparse- Vector (Asi et al.
We first compute the 60040
2023).
18 and then calculate
= [max((. (0, Ta.g" Ta.g)] E 60400x1 where g" arg max, 6040 u=1 ru.g). We generate
6040
the sequence of loss functions (14300(00000) where L, Lu.:- In our experiments, we set m 10, T = 604, E 10, 5 = 0 and run 10 trials. In Fed-SVT, we experiment with communication intervals N 30, 50, where communication cost scales in ( /N). The per-client cumulative regret as 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.
33

---

Stochestic 20. 1000
Stochstiic 10.
Stochark
Por ann Saaree
23
5
Livited Uocatee TeS-0P-O---- -hoth
Uiiitdd Updaiss
Limeee Updatss fedcS--o4F--ten
stach
Mtcchentic Im 10, 100)
Stochariic Cerm 10, 1001
Stochariic (mrm 1001
///
Livited UN00OSs
United Updiites
Uniitdd Updatts
Figure 4: Comparison between Fed-DP-OPE-Stoch and Limited Updates with different random seeds.
Obiivious (teaizabl)) Im 10, = 190)
Cbiiious (Rea Raalzacle) = s- 100)
Oblivious (Rea im 1m d=00
302
5
Soeme-Uesttrr SVt
Meder 14
Sparse Wedtor
Tes-gyT -1
5M Fed
Oblivious [Meelizttee] Jm 10, em 10, 1001
Chivicus (Resizacle) in 1000
(Bealiztteel (m 20. 300
00
1ag
60
Spare--erter
Sparge
Sparge
20
Tec
ned Pec-OOTI
Ted-tVT 50)
Ted-SUT (M:
red-SUT (M
SVT (M
6
110
X6
300
583
133
350
160
z/o
26
100
206
333
dlc
Figure 5: Comparison between Fed-SVT and Sparse-
Sparse-Vector Vector with different random seeds.
H Background on Differential Privacy
H.1 Advanced Composition
Lemma 14 (Advanced composition, Dwork et al. (2014)). AI..... are randomized algorithms
that each is (c, -),D, then their composition (S). Ac(S)) is 1/2l/og(1/8) + ke(e 1), 8' - kDP
H.2 Report Noisy Max
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 a/p( to each count and subsequently determining the index corresponding to the largest noisy count (we ignore the possibility of a tie), where A the sensitivity of the queries. Report noisy max gives us the following guarantee.
34

---

MovieLens-1M
(m 10, == 10)
50
clenct Regret
Sparse-Vector
SVT -0)
20
Fed-SVT 1)
10
100
200
400
500
Figure 6: Regret performance with MovieLens dataset. Shaded area indicates the standard deviation.
Lemma 15 (Dwork al. 2014). Claim 3.9). The Report Noisy Max algorithm is e-differentially
private.
H.3 Sparse Vector Technique
We recall the sparse-vector technique here. Given an input S = (21,..., takes stream of queries Q 92...., @r in an online manner. We assume that each qi is I-sensitive, iee, (S: (S') < 1 for neighboring datasets S, S' E - that differ in single element. We have the following guarantee.
2n)) ) E Z", the algorithm
Lemma 16 (Dwork al. (2014), Theorem 3.24), Let (21..... 2nd E Z". For threshold that halts at time l E [ + 1] such that
and p > 0, there is an E D-DP algorithm
for a 8(log T+log(2/p)) with probability at least 1 p. we have q:(S) L + a for all < k, and or k +
(S) 2 2
I Broader Impacts
This work improves online learning and decision- 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.
35

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
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 perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how be expected to generalize other settings.
much the results
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: See Section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might 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 address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
36

---

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

---

Answer: [Yes]
Justification:
See supplemental material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ ccpppp.ccppulli//uuuii wwwticccguie//eeieeeeeeii CoodeSubeiiie ssi wswonnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
See supplemental material.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: See Appendix E.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support 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, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
38

---

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 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: See Appendix F.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https:
Answer:
[Yes]
Justification:
We make sure follow the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations 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 direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to
39

---

generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: No such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
We do not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, wwppppswpptseeee wwworeewwthhhe....cm com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
40

---

Answer:
[NA]
Justification: No new assets.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/coddemoodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
No crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: No crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
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 expect authors to adhere 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.
41


Reviews:
[{"review_id": "mmPCXoAjdS", "reviewer": "Reviewer_H7Yw", "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.", "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": "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.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Both the theoretical analysis and algorithm design seems original and non-trivial. The technical contribution seems solid. The paper is also clear in its problem setup, algorithm description and theoretical justification. The problem solved by the paper is a concrete theoretical problem, and the paper does a good job in solving the problem overall.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the careful reading and thoughtful comments. We address the reviewer's questions in the following and will revise our paper accordingly. We hope the responses below address the reviewer's concerns. \n\n\n**Q1:** 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. 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.\n\n\n**A1:** Thank you for the helpful comment. Differentially private federated online prediction has many important real-world applications. We provide three examples below, and will add the discussions in our revision.\n\n**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.\n\n\n\n**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.\n\n\n\n**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.\n\n\n\n\n**Q2:** 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.\n\n\n**A2:** Thank you for valuable comment. We have performed experiments on a real-world dataset. Please refer to our Author Rebuttal.\n\n-----\n\nWe thank the reviewer again for the helpful comments and suggestions for our work. We are more than happy to address any further questions that you may have.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vnxdtFLLYr", "reviewer": "Reviewer_NyWa", "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.", "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.\n2, Please clarify the challenges in theoretical analysis given existing methods.", "limitations": "None", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1, The paper is well written, presented: The background, related previous work, problem formulation and key concepts (e.g., federated online prediction, differential privacy, stochastic/oblivious adversaries) are clearly explained. The algorithms are described in detail. \n\n2,  The theoretical analysis appears rigorous, with the authors establishing regret bounds for their proposed algorithms and deriving  lower bounds for the oblivious adversary case. The Fed-SVT algorithm achieves near-optimal regret performance (up to logarithmic factors) in the special case of oblivious adversaries with a low-loss expert, demonstrating the quality of the proposed solution.", "weaknesses": "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.\n\n2, 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?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the careful reading and thoughtful comments. We address the reviewer's questions in the following and will revise our paper accordingly. We hope the responses below address the reviewer's concerns. \n\n\n**Q1:** 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.\n\n**A1:** Thank you for the insightful suggestion. We have performed experiments on a real-world dataset. Please refer to our Author Rebuttal.\n\n**Q2:** 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?\n\n**A2:** The novelty of our theoretical analysis in Theorem 1 is in addressing the unique challenges of a multi-client federated setting, which is not covered in previous works like Asi et al. (2021b, 2022b). While these prior works use a tree-based method for private aggregation of gradients in a single-player context, our approach involves multiple clients who add noise to their gradient estimates locally. This introduces new challenges in establishing the regret upper bound due to the aggregated effect of noisy updates from all clients.\n\nSpecifically, in Fed-DP-OPE-Stoch, each client sends $\\\\{\\langle c\\_n,v\\_{i,j,s} \\rangle +\\xi\\_{i,n}\\\\}\\_{n\\in [d]}$, where $\\xi\\_{i,n}\\sim \\text{Lap}(\\lambda\\_{i,j,s})$, and $\\lambda\\_{i,j,s}= \\frac{4\\alpha2^j}{b\\varepsilon}$. The server aggregates these to predict a new expert, i.e., $\\bar{w}\\_{j,s}=\\underset{c\\_n: 1\\leq n\\leq d}{\\arg\\min}\\left[\\frac{1}{m}\\sum_{i=1}^m \\big( \\langle c\\_n,v\\_{i,j,s} \\rangle + \\xi\\_{i,n} \\big) \\right]$. \n\nThe key novelty and challenge are in handling the noisy estimates aggregated from multiple clients ($\\frac{1}{m}\\sum_{i=1}^m \\big( \\langle c_n,v_{i,j,s} \\rangle + \\xi_{i,n} \\big)$) and analyzing its impact on the regret upper bound. To handle the impact of the average estimates $\\frac{1}{m}\\sum_{i=1}^m \\langle c_n,v_{i,j,s} \\rangle$, we show in Lemma 2 that every index of the $d$-dimensional vector $\\nabla L\\_{t}(x\\_{i,p,k})-\\bar{v}\\_{p,k}$ is $O(\\frac{1}{bm})$-sub-Gaussian by induction on the depth of vertex. This enables us to achieve $\\sqrt{m}$-fold regret speed-up compared with Asi et al. (2022b). To deal with the challenge introduced by the aggregated noise $\\frac{1}{m}\\sum_{i=1}^m \\xi_{i,n}$, we introduce Lemma 4, which quantifies the bound on the sum of $m$ IID Laplace random variables. This differentiates our analysis from prior single-client studies (Asi et al. 2021b, 2022b). \n\nAdditionally, the federated setting poses challenges in reducing communication costs while maintaining privacy. Our Fed-DP-OPE-Stoch algorithm introduces a strategic communication protocol where communication is triggered only when the DP-FW subroutine, used for private gradient aggregation at each client, reaches a leaf vertex in the binary tree structure (Line 7-8 in Algorithm 1). This approach contributes to the overall reduction in communication costs, achieving logarithmic communication costs (Corollary 1). This aspect of Fed-DP-OPE-Stoch is another novel contribution, addressing the critical challenge of efficient communication in the federated setting. In comparison, Asi et al. (2021b, 2022b) focus on single-player settings and do not involve methods to control the communication cost.\n\n**Q3:** 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. \n\n**A3:** Thanks for the suggestion. We include it in our Author Rebuttal.\n\n**Q4:** Please clarify the challenges in theoretical analysis given existing methods.\n\n**A4:** We present the following challenges and contributions in the theoretical analysis.\n\n1. Regret Upper Bound for Stochastic Adversaries: The challenges in the theoretical analysis of Fed-DP-OPE-Stoch and our contributions are detailed in **A2**. \n\n2. Novel Lower Bounds for Oblivious Adversaries: We establish new lower bounds for federated OPE with oblivious adversaries, showing that collaboration among clients does not lead to speed-up in regret minimization (Theorem 2). The key challenge is formulating an instance of oblivious adversaries where the collaborative nature of federated learning does not result in the expected improvements in regret minimization. To address this, we propose a novel *policy reduction approach in FL*, representing a technical breakthrough (highlighted in the proof sketch of Theorem 2). Specifically, 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, showing the equivalence of per-client and single-player regret. To the best of our knowledge, our lower bounds represent the **first** of their kind for differentially private federated OPE problems.\n\n3. Lower Bound for Oblivious Adversaries under Realizability Assumption: We establish a new lower bound in this setting (Theorem 3). Our analysis considers a specific oblivious adversary (detailed in the proof sketch of Theorem 3), which differentiates it from single-player scenarios (Asi et al., 2023). Our lower bound indicates that Fed-SVT is nearly optimal up to logarithmic factors (Remark 6). \n\n---\n\nWe 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xXPFn0xs3a", "reviewer": "Reviewer_RFE1", "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.", "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?\n2. 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": "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$.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper proposes differentially private online federated learning algorithm which is an important and unexplored research area.\n2. The paper provides regret analysis with differential privacy guarantees for the proposed algorithms. Although I am not expert at differential privacy, theoretical results looks convincing to me.\n3. The paper is well-written and clear.", "weaknesses": "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.\n2. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the careful reading and thoughtful comments. We address the reviewer's questions in the following. We hope the responses below address the reviewer's concerns. \n\n**Q1:** The paper can benefit from extending its experimental study. \n\n**A1:** Thanks for the helpful suggestion. We have performed experiments on a real-world dataset. Please refer to our Author Rebuttal.\n\n**Q2:** The paper can add more explanations about applicability of the study. \n\n**A2:** Thanks for the insightful suggestion. In this work, we focus on differentially private federated online prediction, where the objective is to minimize the average regret on $m$ clients working in parallel while maintaining the privacy of users at each client. Differentially private federated online prediction has many important real-world applications. We provide three examples below, and will add the discussions in our revision.\n\n**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 the prediction accuracy without exposing individual's health data, thus ensuring patient privacy.\n\n**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.\n\n**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.\n\n**Q3:** Can you explain more about the statement 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\"?\n\n**A3:** Thank you for your insightful comments. In federated learning, training data is distributed across an incredibly large number of devices, each potentially having limited communication bandwidth to the central server [1]. Consider the hospitals within an area as the set of clients, each aiming to make accurate predictions (e.g. diagnostic) for its own patients. Then, the loss function for each client depends on the healthcare history of all patients in the hospital. Obviously, transmitting patients' healthcare histories from all hospitals to a central server frequently requires a lot of communication bandwidth and is often time-consuming. One major motivation for federated learning is to avoid transmitting raw data (e.g., loss functions) to the central server, while maintaining learning performances comparable with the centralized setting [2-5].  \n\nMoreover, keeping raw data (e.g., loss functions) at local clients in federated learning is also beneficial for **privacy protection**. Intuitively, to protect the loss function transmitted every round, we need to apply DP mechanism to privatize each loss function (e.g. Laplacian noise $\\text{Lap}(\\frac{1}{\\varepsilon})$), as exposing sensitive patient data is a concern. Such a noise level will compromise the data accuracy at the server, and leads to significant learning performance degradation. In contrast, under an efficient communication protocol of federated learning, the noise level added during each communication round can be significantly reduced, since we don't have to protect each loss function but certain information extracted from multiple loss functions. For example, in Fed-DP-OPE-Stoch, each client adds Laplacian noise with standard deviation $O(\\frac{1}{2^{p-1}\\varepsilon})$ to the estimated gradients before transmission in phase $p\\in [\\log T]$. Such reduced noise level has minimum impact on the aggregated gradient estimate at the server, and results in near-optimal privacy-utility trade-off.\n\nIn summary, due to both communication cost and privacy considerations, designing communication-efficient learning algorithms is of critical importance in the federated setting. In this work, we follow the standard federated learning principle to keep raw data (loss functions) at the clients, and design communication-efficient federated online prediction algorithms. We thank the reviewer again for the comment and will revise the statement in the paper to avoid possible confusion. \n\n**Q4:** I suggest extending the literature review of the paper by including the work \"Personalized online federated learning with multiple kernels\". \n\n**A4:** Thank you for the suggestion. We will include the recommended work and provide a literature review on (federated) online model selection in Appendix A as follows.\n\n**(Federated) Online Model Selection:** Online model selection when models are kernels has been extensively studied [6-9]. In the federated setting, [10,11] have explored scenarios where each client learns a kernel-based model, utilizing the specific characteristics of kernel functions. Moreover, [12] proposes an online federated model selection framework, where clients interact with a server with sufficient memory. Additionally, research on online learning with feedback graphs, a generalization of sequential decision-making with bandit or full information feedback, has been explored in [13-19].", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "MjoU3diYEu", "reviewer": "Reviewer_hhm9", "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. \n\nThe 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.", "questions": "Could you please clarify what is the link between sensitive data and the notion of neighboring input used in the paper? \n\nFor 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": "The limitations of the work have been appropriately addressed by the authors.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper is in general clearly written.\n\nThe contributions provide a significant impact, showing that federated collaboration can improve accuracy under privacy constraints without incurring in large communication cost (i.e. the cost is logarithmic in $T$ for the stochastic adversary setting). The $\\sqrt{m}$ factor speedup is significant. The relaxation of the oblivious adversary seems realistic, therefore improvements in this setting seem also important. \n\nThe paper also proposes novel techniques. Although the natural adaptation to federated setting and the use tree based private aggregation have been widely studied in the past, the paper also proposes novel ways to reduce (i) communication in the stochastic adversary setting, (ii)  regret and communication in the (relaxed) oblivious adversary setting and (iii) a novel proof technique for the lower bounds on the classical oblivious case. \n\nThe work is of good quality, appropriately backing it's claims with proofs and empirically illustrating the impact of the results with reproducible experiments.", "weaknesses": "There are certain non-major weaknesses in motivating the problem and clarity at preliminaries:  \n\n1- The implications of accurate OPE could be better motivated in the introduction. \n\n2- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the careful reading and thoughtful comments. We address the reviewer's questions in the following and will revise our paper accordingly. We hope the responses below address the reviewer's concerns. \n\n\n**Q1:** There are certain non-major weaknesses in motivating the problem and clarity at preliminaries: The implications of accurate OPE could be better motivated in the introduction.\n\n**A1:** Thank you for your helpful comment. We will clarify the implications of accurate OPE in the introduction as follows:\n\nOPE is an important problem in machine learning with various applications. For example, in personalized healthcare, a patient's wearable device (player) collects and processes health data to provide personalized health treatment (experts). OPE helps select the most effective treatments based on historical data, improving patients' outcomes.\n\nWe will include this to better highlight the implications of OPE in our revised introduction.\n\n**Q2:** 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.\n\n**A2:** Thank you for your insightful comments. We will clarify the notion of DP in the online setting in the revision.\n\n1. Link Between Loss Functions and Sensitive Data: The sequence of loss functions $\\mathcal{S}=\\left(l_{1,1}, \\ldots, l_{m,T}\\right)$ represents the sensitive dataset since each loss function $l_{i,t}$ reflects the performance of selecting different experts based on sensitive information about client $i$ at time step $t$.\n\n2. Terminology Confusion: To clarify, the OPE adversary refers to the entity selecting the sequence of loss functions to challenge the online algorithm, while the DP adversary represents a potential attacker trying to infer sensitive information from the algorithm's outputs. We will revise the preliminary section to distinguish these roles clearly, referring to the OPE adversary as the \"game adversary\" and the DP adversary as the \"privacy adversary\". \n\n**Q3:** 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 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.\n\n**A3:** Thank you for the question. In our setting, the sequence of loss functions $\\mathcal{S}=\\left(l_{1,1}, \\ldots, l_{m,T}\\right)$ is considered the sensitive dataset and we define neighboring datasets as sequences that differ by a single loss function. Our setting is applicable when protecting individual loss functions is sufficient. For example, in a personalized recommendation system, each user's interaction with content (e.g. articles) generates a loss function. Our setting ensures that changing a single interaction does not significantly influence the system's recommendations, protecting individual user interactions. This is suitable for applications like personalized content recommendations, where protecting individual interactions is essential while still allowing for effective personalization.\n\nWe understand that the reviewer's example describes a stronger DP setting, where one sensitive data point may affect multiple loss functions, and all of those loss functions need to be protected simultaneously. In some sense, we can view one data point as a user, and each user may contribute multiple loss functions. Thus, to protect individual users, it is necessary to protect all loss functions that each user contributes. This essentially gives rise to **user-level DP** [1]. We note that user-level DP in general is much more challenging to handle [2-6] compared with instance-level DP discussed in this work, and we leave it as one of the important future directions to explore.\n\n[1] Levy D, Sun Z, Amin K, et al. Learning with user-level privacy[J]. Advances in Neural Information Processing Systems, 2021, 34: 12466-12479.\n\n[2] Liu Y, Suresh A T, Yu F X X, et al. Learning discrete distributions: user vs item-level privacy[J]. Advances in Neural Information Processing Systems, 2020, 33: 20965-20976.\n\n[3] Acharya J, Liu Y, Sun Z. Discrete distribution estimation under user-level local differential privacy[C]//International Conference on Artificial Intelligence and Statistics. PMLR, 2023: 8561-8585.\n\n[4] Cummings R, Feldman V, McMillan A, et al. Mean estimation with user-level privacy under data heterogeneity[J]. Advances in Neural Information Processing Systems, 2022, 35: 29139-29151.\n\n[5] Ghazi B, Kumar R, Manurangsi P. User-level differentially private learning via correlated sampling[J]. Advances in Neural Information Processing Systems, 2021, 34: 20172-20184.\n\n[6] Huang R, Zhang H, Melis L, et al. Federated linear contextual bandits with user-level differential privacy[C]//International Conference on Machine Learning. PMLR, 2023: 14060-14095.\n\n-----\n\nWe thank the reviewer again for the helpful comments and suggestions for our work. We are more than happy to address any further questions that you may have.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all reviewers for their feedback, which has greatly improved our paper. We are glad that our work is recognized for studying "an important and unexplored research area" (Reviewer RFE1) and developing Fed-DP-OPE-Stoch with "novel techniques" (Reviewer hhm9) to handle stochastic adversaries, as well as a "novel proof technique" (Reviewer hhm9) for lower bounds in the classical oblivious case. Our Fed-SVT algorithm achieves near-optimal regret in a near-realizable case of oblivious adversaries, "demonstrating the quality of the proposed solution" (Reviewer NyWa). Our theoretical analysis and algorithm design are "original and non-trivial" (Reviewer H7Yw) and we "empirically illustrate the impact of the results with reproducible experiments" (Reviewer hhm9). Below, we address a common question the reviewers have. 

**Could you perform experiments on real-world dataset scenarios? (Reviewers: H7Yw, NyWa, RFE1)**

We use the MovieLens-1M dataset [1] to evaluate the performances of Fed-SVT, comparing it with the single-player model Sparse-Vector [2]. We first compute the rating matrix of 6040 users to 18 movie genres (experts) $R = [r\_{u,g}] \in \mathbb{R}^{6040\times 18}$, and then calculate $L = [\max (0,r\_{u,g^\star}-r\_{u,g})]\in \mathbb{R}^{6040\times 18}$ where $g^\star = \arg \max\_g \left( \frac{1}{6040} \sum_{u=1}^{6040} r\_{u,g} \right)$. We generate the sequence of loss functions $\\{l\_u\\}\_{u\in [6040]}$ where $l\_u = L\_{u,:}$. In our experiments, we set $m=10$, $T = 604$, $\varepsilon = 10$, $\delta = 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 1 in our uploaded PDF file. Our results show that Fed-SVT significantly outperforms Sparse-Vector [2] with low communication costs (notably in the $N=50$ case). These results demonstrate the effectiveness of our algorithm in real-world applications. We will perform more experiments to thoroughly validate the performance of both Fed-SVT and Fed-DP-OPE-Stoch, and include the results in the next version of this paper.

References

[1] Harper F M, Konstan J A. The movielens datasets: History and context[J]. Acm transactions on interactive intelligent systems (tiis), 2015, 5(4): 1-19.

[2] Asi H, Feldman V, Koren T, et al. Near-optimal algorithms for private online optimization in the realizable regime[C]//International Conference on Machine Learning. PMLR, 2023: 1107-1120.

Meta-review: 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.
Decision: Accept (poster)