Communication-Efficient Federated Non-Linear Bandit Optimization
Authors: Chuanhao Li
Chong Liu
Yu-Xiang Wang
Venue: ICLR 2024 poster (2024)
Keywords: federated optimization
communication cost
non-linear bandit
bandit optimization
cumulative regret
Primary area: optimization
TL;DR: federated bandit optimization of generic non-linear objective function

Abstract: Federated optimization studies the problem of collaborative function optimization among multiple clients (e.g. mobile devices or organizations) under the coordination of a central server. Since the data is collected separately by each client and always remains decentralized, federated optimization preserves data privacy and allows for large-scale computing, which makes it a promising decentralized machine learning paradigm. Though it is often deployed for tasks that are online in nature, e.g., next-word prediction on keyboard apps, most works formulate it as an offline problem. The few exceptions that consider federated bandit optimization are limited to very simplistic function classes, e.g., linear, generalized linear, or non-parametric function class with bounded RKHS norm, which severely hinders its practical usage. In this paper, we propose a new algorithm, named Fed-GO-UCB, for federated bandit optimization with generic non-linear objective function. Under some mild conditions, we rigorously prove that Fed-GO-UCB is able to achieve sub-linear rate for both cumulative regret and communication cost. At the heart of our theoretical analysis are distributed regression oracle and individual confidence set construction, which can be of independent interests. Empirical evaluations also demonstrate the effectiveness of the proposed algorithm.

Published as a conference paper at ICLR 2024
COMMUNICATIOO-EEFICENN FEDERATED
NON-
LINEAR BANDIT OPTIMIZATION
Chuanhao Li Chong Liu
Yu-Xiang Wang
Yale University TUniversity of Chicago UUniversity of California, Santa Barbara chuanhac. 11. Li..cl2378yyale... edu chongl@uchi edu yuxiangwecs ucsb edu
ABSTRACT
Federated optimization studies the problem of collaborative function optimization among multiple clients (c.g. mobile devices or organizations) under the coordina- tion of central server. Since the data is collected separately by each client and always remains decentralized, federated optimization preserves data privacy and allows for large-scale computing. which makes a promising decentralized ma- chine learning paradigm. Though is often deployed for tasks that are online nature, e.g., next-word prediction on keyboard apps, most works formulate it as an offline problem. The few exceptions that consider federated bandit optimization are limited very simplistic function classes, e.g., linear, generalized linear, or non non-parametric function class with bounded RKHS norm, which severely hinders practical usage. In this paper, we propose a new algorithm, named Fed-Gr UCB, for federated bandit optimization with generic non-linear objective func- tion. Under some mild conditions, we rigorously prove that Fed-GO-UCB able achieve sub-lineat rate for both cumulative regret and communication cost. At the heart of our theoretical analysis are distributed regression oracle and individ- ual confidence construction, which be of independent interests. Empirical evaluations also demonstrate the effectiveness of the proposed algorithm.
INTRODUCTION
Federated optimization is machine learning method that enables collaborative model estimation over decentralized dataset without data sharing (McMahan et al.] 2017)] Kairouz et al.] 2019). allows the creation of shared global model with personal data remaining local sites instead of being transferred to central location, and thus reduces the risks of personal data breaches. While the main focus of the state-of-the of-the-art federated optimization is on the offline setting, where the objective is to obtain a good model estimation based on fixed dataset (Li et al. 2019a Mitra et al., 202I). several recent research efforts have been made to extend federated optimization the online setting, i.e., federated bandit optimization (Wang et al. 2020 Li& Wang 2022b Li et al. 2022a).
Compared with its offline counterpart, federated bandit optimization is characterized by its online interactions with the environment, which continuously provides new data points to the clients over time. The objective of the clients is collaboratively minimize cumulative regret, which measures how fast they can find the optimal decision, as well as the quality of decisions made during the trial- and-error learning process. This new paradigm greatly improves sample efficiency, the clients not only collaborate model estimation, but also actively select informative data points to evaluate in a coordinated manner. Moreover, compared with the standard Bayesian optimization approach Shahriari et al. 2015)), the improved data protection of federated bandit optimization makes it a bet- ter choice for applications involving sensitive data, such as recommender systems (Li et al., 2010), clinical trials (Villar et al., 2015) and sequential portfolio selection (Shen et al. 2015). For exam- ple, medical data such as disease symptoms and medical reports are very sensitive and private, and typically stored in isolated medical centers and hospitals (Yang et al., 2019). Federated bandit optimization offers a principled way for different medical institutions to jointly solve optimization problems for smart healthcare applications, while ensuring privacy and communication efficiency.
"Equal Contribution

---

Published as a conference paper at ICLR 2024
Client
1Z711
select point xz
6r
Client (
Vlaya
Ri
DTey, Aby
Ding Alia
Unknown function f
Client
sloue
Server
6
Al al &hi,
Server
reeeive Doisy feedbbuck
Phuse (Uniform exploration)
Phase II (Optimistic exploration)
U(X)
X2 argmax
maa
f2(W)
XEX
WEBall
Figure 1: Illustration of Fed-GO-UCB algorithm, which consists of two phases: in Phase I, all clients do uniform exploration for a total number of To time steps, and then use the collected data to jointly construct an model th via iterative distributed optimization; in Phase II, each client constructs local confidence set for the unknown non-linear function f using gradients w.r.t. the shared model wo, based which they do optimistic exploration. Synchronization of their local statistics happens when a communication event is triggered, which enables coordinated exploration among the clients.
However, despite these potential benefits and the compelling theoretical guarantees, prior works in this direction are limited to very restrictive function classes, e.g., linear (Wang et al. 2020 Li &
Wang 2022a He et al. 2022), generalized linear (Li & Wang 2022b). and non-parametric function
class with bounded RKHS norm (Li et al. 2022a 2023 Du et al. 2021), which limits their potential in practical scenarios that typically require more powerful tools in nonlinear modeling, e.g. neural networks. The main challenges in bridging this gap come from
aspects. First, different from offline federated optimization, federated handit optimization needs to efficiently explore the decision space by actively picking data points to evaluate. This requires a careful construction of confidence sets for the unknown optimal model parameter (Abbasi-yadkori et al. 2011), which is challenging for generic nonlinear functions. Second, for clients collaboratively estimate confidence sets, occasional communications are required to aggregate their local learning parameters as new data points are collected over time. Prior works consider simple function classes (Wang et al., 2020 Li & WWang 2022a), so efficient communication can be realized by directly aggregating local sufficient statisties for the closed-form model estimation. However, generic non-linear function places a much higher burden on the communication cost, as iterative optimization procedure is required.
To address these challenges, we propose the Federated Global Optimization with Upper Confidence Bound (Fed-GO-UCB) algorithm, illustrated in Figure I Specifically, Fed-GO-UCB has two phases: Phase does uniform exploration to sufficiently explore the unknown function; and Phase Il does optimistic exploration to let N clients jointly optimize the function. All clients separately choose which points to evaluate, and only share statistics summarizing their local data points with the central server. Details of Fed-GO-UCB
presented in Section 4.1
Technical novelties. Our core technique to address the aforementioned challenges is a novel con- fidence sets construction that works for generie nonlinear functions, and more importantly, can be updated communication efficiently during federated bandit optimization. Our construction is moti- vated Liu Wang 2023), with non-trive non-trivial extensions tailored federated bandit setting. Specif- ically, the statistics used for function approximation in Liu & Wang (2023) is computed based on single sequence of continuously updated models. but in federated bandits, each client has a different sequence of locally updated models. Direct aggregation of such local statistics does not necessar- ily lead to valid confidence sets. Instead, we propose new approximation procedure, such that all statistics are computed based on the same fixed model shared by all clients, which is denoted by up. With improved analysis, we show that valid confidence sets can still be constructed. More importantly, this allows direct aggregation of statistics from different clients, that communication strategies proposed in linear settings can be utilized to reduce frequency of communications. Over the entire horizon, only the estimation of úo at the end of Phase requires iterative optimization. To further control the communication cost it incurs, show that un only needs be O(I/VNT)-
2

---

Published as a conference paper at ICLR 2024
approximation to the empirical risk minimizer that is required in the analysis oiu & Wang 2023 and adopt a distributed implementation of Gradient Langevin Dynamics (GLD) for its optimization.
Contributions. Our main contributions can be summarized as follows.
To the best of our knowledge, this is the first federated bandit algorithm for generic non-linear function optimization with provable communication efficiency, making it deployment-efficient.
Under realizable assumption and some other mild conditions, we prove that cumulative regret of
Fed-GO-UCB is Ö(vNT) and its communication cost is ((N15V))
Our empirical evaluations show Fed-GO-UCB outperforms existing federated bandit algorithms, which demonstrates the effectiveness of generic non-linear function optimization,
RELATED WORK
Centralized global optimization Most work on global optimization studies the centralized setting where all data points are available on a single machine. Its applications include hyperparameter
luning for deep neural networks (Hazan et al. 2018
Kandasamy al., 2020) and materials design The most popular approach to this problem is Bayesian optimization (BO) (Shahriari et al.) 2015 Frazier 2018). which is closely related bandit
(Nakamura et al. 2017: Frazier& & Wang 2016).
problems (Li et al., 2019b] Foster & Rakhlin (020). BO typically assumes the unknown objective function is drawn from some Gaussian Processes (GP). The learner sequentially choose points to evaluate and then improve its estimation via posterior update. Classical BO algorithms include GP- UCB (Srinivas et al. 2010). GP-EI (Jones et al.] 1998). and GP-PI (Kushner) [964). To improve heterogencous modeling of the objective function and mitigate over-exploration, Trust region BO (Eriksson et al. 2019) that uses multiple local optimization runs is proposed. In this line of research, the closes work to ours is Liu & Wang (2023), which also considers global approximation of generic
nonlinear functions, though it's not suitable for federated setting as discussed in Section [
Federated bandit optimization Another closely related line of research is federated/dissributee bandits, where multiple agents collaborate in pure exploration (Hillel et al. 2013) Tao et al.) 2019
Du et al. (02T). or regret minimization (Wang al. [220 Li & Wang 2022a bp. However, most of these works make linear model assumptions, and thus the clients can efficietlly collaborate by transferring the ((d)) sufficient statisties for closed-form model estimation, where de is input data dimension. The closest works to ours are Wang et al. 22000) Dubey & Pentland (2020); Li & Wang 2022a b). which uses event-triggered communication strategies to obtain sub-linear communication cost over time, i.e., communication only happens when sufficient amount of new data has been collected. There is also recent work by Dai et al. (2022) that studies federated bandits with neural function approximation, but it still relies on GP with a Neural Tangent Kernel in their analysis, which intrinsically linear. More importantly, this analysis assumes the width of the neural network is much larger than the number of samples, while our results do not require such over parmeterrizatinn
3 PRELIMINARIES
We consider the problem of finding a global maximum solution to an unknown non-linear black-box function f. i.e..
arg max (x).
xEX
Different from previous works, we consider decentralized system of 1) N clients that selects data points to evaluate, and 2) a central server that coordinates the communication among the clients. The clients cannot directly communicate with each other, but only with the central server, i.c., star-shaped communication network as shown in Figure I] In each round, N clients interact with the unknown function in round-robin manner, for a total number of T rounds, so the total number of Specifically, at round / E [T]] each
interactions is NT'. Let [N] denote the integer set {1, .,.,,N,, N). client i [N] selects a point x, from the set X, and has zeroth-order noisy function observation:
= fxx) + 7) E TR
(1)
where the subscript t := N(1 1) i indicates this is the t-th interaction between the system and the function f. i.e., the f-th time function f is evaluated at a selected point X,, and f). is independent, zero-mean,
noise, for E [NT].
3

---

Published as a conference paper at ICLR 2024
We adopt the classical definition of cumulative regret evaluate the algorithm performance. It is defined RvT E [(x*) f(x)) for NT interactions. Following Wang et al. 2020)), define the communication cost CNT as the total amount of real numbers being transferred across the system during the NT' interactions with function f.
Let U denote uniform distribution. W.l.ogg,, let X C [0, 1j4 and y C R denote the domain and range of unknown function f. We are working with a parametric function class FF := {fw : X + V/ww E W) to approximate f where the parametric function class is controlled by the parameter space W. For a parametric function (x),, let (=) denote the gradient taken w.rt. a and (w) denote the gradient taken w.r.t. w. We use it E [N] as the index of the client that evaluates point 2, at time step f. We denote the sequence of time steps corresponding to data points that have been evaluated by client i up to time t as Dí, {1 S t i, = i} for & 1, 2, ................................ NT. In addition, we denote the sequence of time steps corresponding to the data points that have been used to update client i's local model as Di.,, which include both data points collected locally and those received from the server. If client i never receives any communication from the server, Dr.- Di,5; otherwise, Di, C Dr, S [t]. Moreover, when each new data point evaluated by any client in the system is readily communicated to all the other clients, we recover the centralized setting, i.e., Dr.; = [4, Vi,l. I. For completeness, we list all notations in Appendix A
Here we list all assumptions that we use throughout this paper. The first two assumptions are pretty standard and the last assumption comes from previous works.
Assumption (Realizabilty). There exists w' E W such that the unknown objective function f = fwr. Also, assume W c. 1j This is w.l.o.g. for any compact W. Assumption (Bounded, differentiable and smooth function approximation). There exist constants F, Cg. CA 0, s.t. Ifx s F. fu) Cg. and fu))llo I Ch. Vr X, w E W. Assumption 3 (Geometric conditions on the loss function (Liu & Wang [003] Xu et al. 2018)) ). L(w) = Ex=u((f( - [=(2"))² satisfies (T, (Tgoowht condition or local p-strong convexity at w", Le, Ve E W,
4 min
w fw- w0
T || w w=1l2 S L(w) - L(ww),
2
2
for constants J > 0, < d < 7 <
L(w) satisfies dissipative ussumption, i.e.,
(L(w) w 2 C, [ for some constants C, Cj > 0. and a c-local self-concordance assump-
tion at w², i.e. (1 c) VV"L("" = (( = (1 (a--c)--0 ")""" Ywu s.f. ||w w" [[va S c.
Assumption 2 implies there exists a constant Ç > 0, such that ||VL(w"))lo S Ç. For example, suffices to take <= 2C2 Assumption made on the expected loss function L w.r.t parameter rather than function f. and is strictly weaker than strong convexity as it only requires strong convexity in the small neighboring region around w". For w far away from w", L(w) can be highly non-convex since only growth condition needs to be satisfied. The dissipative assumption is typical for stochastic differential equation and diffusion approximation (Raginsky et al. 2017 Zhang et al.) 2017). In our paper, it is only needed for the convergence analysis of Algorithm 2 and may be relaxed by adopting other non-convex optimization methods with global convergence guarantee.
4 METHODOLOGY
4.1 FED-GO-UCB ALGORITHM
In this paper, we develop an algorithm that allows Bayesian optimization style active queries to work for general supervised learning- -ased function approximation under federated optimization scheme.
Phase I
In Step 1 of Phase I, the algorithm evaluates the unknown function f at uniformly sampled points for a total number of To times, where To is chosen to be large enough such that function f can be sufficiently explored. By the end of time step To. each client i E [N] has collected a local dataset {(x,, ya)} sE D),, (by definition USE(N Dr.,; = [T)]). In Step 2, we call the distributed regression oracle, denoted as Oracle, to jointly learn model parameter wh. by optimizing equation 2 below.
N
Σ (w), min (w) = To 1=1 weW
(2)
4

---

Published as a conference paper at ICLR 2024
Algorithm Fed-GO-UCB
Input: Phase I length To. Time horizon (Phase II length) NT, Oracle, number of iterations to execute Oracle, communication threshold regularization weight X. Phase I (Uniform exploration)
1: for t= 2, , To do client in E [N] evaluates point v, ~ ((),, and observe y/
2: Execute Oracle (e.g.. Algorithm 2 over N clients to obtain úo
Phase II (Optimistic exploration)
1: Initialize VT.. = thg ETg = AI bTo = 0, Dra. = 0, for each client i [N]
2: for t = ..... NT do
3: Client & evaluates point #t = arg m max 1.1, f2(w) and observe y/: fz,
4: Client is updates Ee,i = E1- + V fz. fz, (200) by.
61-1.6 + A + fz, (wo) V fu. (200)
V fx, (wo) (100) 200 + - fa,), and A ACr,
Abr,i, = Abr- + Vzz, (wo) (wo)) "0p + 3/ Sz.
5: Client updates Wr,i, by equation 5 and Ball,, by equation
sets index De.ie
DE-L& U (t}
# Check whether global synchronization is triggered
6: if ((Dr,,, I 1) log det(E - ....;,)
det(Er...)
then
7:
All clients upload {AEt,i, Abr, and reset A Λ 0, Abt,: for I,....N Server aggregates Dt.g = 2 + E A begg = blangg + Σi= Abr,t
8:
9:
All clients download (2e..g b and update E Di.g br, = b for I...,,N N
10: Set fims =t
Output: f ((111...., IT))
where (wo = DS [v. - [x is the squared error loss on client i's local dataset. It is
worth noting that, executing Oracle to compute the exact minimizer úi := arg min LT, (w) as in the prior work by Liu & Wang (022) is unreasonable in our case, since it requires infinite number of iterations, which leads to infinite communication cost. Instead, we need to relax the requirement by allowing for approximation error such that Oracle only need to output the that satisfies
LTo (wo) - LT, (w%)) S.
(3)
Oracle can be any distributed non-convex optimization method with global convergence guarantee, i.e. we can upper bound the number of iterations required, denoted as n, to attain c, for some c 2 0.
Remark 4. In this paper adopt Gradient Langevin Dynamics (GLD) based methods optimize equation 2 which are known to have global convergence guarantee to the minimizer of non-convex objectives under smooth and dissipative assumption (Assumption 2ad Assumption B). GLD based methods work by introducing a properly scaled isotropic Gaussian noise to the gradient descent up- date at each iteration, which allows them to escape local minima. Specifically, use distributed implementation of GLD, which is given in Algorithm 2 It requires
0 -log(E)) iterations to altain approximation (with step size set to TI S <), where v O denotes the spectral gap of the discrele-time Markov chain generated by GLD (Theorem 3.3 of ofXu el al. (0118).
Algorithm Distributed Distriuted-GLD-Uppaeee GLD-Update
1: Input: total iterations n;; step size Tı > 0; inverse temperature parameter T2 > 0; (0 = 0
2: for k 0, 1,...;
do 3: Server sends (k)) to all clients, and receives local gradients Vir, (w(()) for E [N] back
4: Server aggregates local gradients LL, (w(()) = To DN LL, (w)())
5: Server randomly draws 2 ~ Ixx))
6: Server computes update (A++1) wk(k) Vir, (wolk) + 2
7: Output: wo = (K)
Phase II
At the beginning of Phase II, the estimator wn obtained in Phase I is sent to each client, which will be used to construct the confidence sets about the unknown parameter w². Specifically,
5

---

Published as a conference paper at ICLR 2024
at each time step 1, .T, the confidence set constructed by client is a ball defined as Ball, == {w || wr 12..... I Ste,b
(4)
such that with the choice of Sr, in Lemma 8 wt Ball Vt with probability at least 1 - 8. The center of this ball is defined as
We,, E bes. A Wp,
(5)
where the matrix
Σei = +I E
Vix, (10) Vxx. (wo)
(6)
DED
and vector be,i, = E.EDD. (wo) [V (wo) To ys fx. (wo)] Note Vfx, (w)) is the gradient of our parametrie function taken w.r.t parameter Vo. rather than the gradient of the un- known objective function. The statistics E,,, be,; for all client i and time t are constructed using gradients w.r.t. the same model zog. This is essential in federated bandit optimization, as it allows the clients to jointly construct the confidence set by directly aggregating their local updates, denoted by AEt. Abr In comparison, although the statistics used to construct the confidence sets in Liu & Wang 2023) computed based different models and lead to tigher results, they impede collaboration among clients and cannot be directly used in our case.
In Phase II, exploration is conducted following "Optimism in the Face of Uncertainty (OFU)" prin- ciple, i.e., at time step f, client is selects point x, E X' to evaluate via joint optimization over x E X and Ball;-1.i.- as shown in line 3. The newly obtained data point (xe, 34) will then be used to update client i, 's confidence set as shown in line 4-5. In order to ensure communication efficiency during the collaborative global optimization across N clients, an event-triggered communication protocol is adopted, as shown in line 6. Intuitively, this event measures the amount of new informa- tion collected by client b since last global synchronization. If the value of LHS exceeds threshold y, another global synchronization will be triggered, such that the confidence sets of all N clients will be synchronized as shown line 7-9. In Section we will show that with proper choice of 7, the total number of synchronizations can be reduced to Ö(VN), without degrading the performance.
4.2 THEORETICAL RESULTS
Theorem 5 (Cumulative regret and communication cost of Fed-GO-UCB), Suppose Assumption 7 2 and 3 hold. Let C denote a universal constant and C) denote a constant that is independent
(17/(227) __²² 122 where is the logarithmic T. Under the condition that 2 Cdf. .max 737(2-5)' ue=
term depending To. Oho and 2/5. Algorithm [
with parameters To VNT, X CAVNT,
7 du F and S CVNT' has cumulative regret N
8
Rohase I phuse Ô
(v (VNTF+ VNT No. Fd/FF/11²
with probability at least 8, and communication cost
Ophase phuse II = Ö /Tyn exp (de) + N1 Pu F2))
Theorem shows that our proposed Fed-GO-UCB algorithm matches the regret upper bound of its centralized counterpart, GO-UCB algorithm by Liu & Wang (023). while only requiring commu- nication cost that is sub-linear in T. We should note that the O(VT) dependence in communication cost is due to the iterative optimization procedure to compute wh at the end of Phase I, which also exists for prior works in federated bandits that requires iterative optimization (Li & Wang (022b).
PROOF OVERVIEW
In this section, to highlight our technical contributions, provide proof sketch of the theoreti- cal results about cumulative regret and communication cost that are presented in Theorem 5 All auxiliary lemmas given in Appendix Cadd complete proofs are presented in Appendix D

---

Published as a conference paper at ICLR 2024
5.1 PHASE I. UNIFORM EXPLORATION & DISTRIBUTED REGRESSION ORACLE
Cumulative Regret and Communication Cost in Phase Recall from Section 4.1 that, N clients conduct uniform exploration in Phase which constitutes a total number of To interactions with the environment. By Assumption 2 we know that the instantaneous regret has a unform upper bound r: := - fxx) S 2F, so for a total number of To time steps, the cumulative regret incurred in Phase I, denoted as Retase can be upper bounded by Rptase = - Pt I F. Choice of To value will be discussed in Section (.2 as it controls the quality of the which further affects the constructed confidence sets used for optimistic exploration.
Moreover, the only communication cost in Phase I is incurred when executing Oracle, i.e., the distributed regression oracle, for n iterations. In each iteration, N clients need to upload their local gradients the server, and then receive the updated global model back (both with dimension dwe). Therefore, the communication cost incurred during Phase I is Ophase 2n
Distributed Regression Oracle Guarantee At the end of Phase I, we obtain an estimate dog by optimizing equation 2 using Oracle. As we mentioned in Section 4.2 do will be used to construct the confidence sets, and thus to prepare for our analysis of the cumulative regret in Phase II, we establish the following regression oracle lemmas.
Lemma 6. There is an absolute constant C', such that after time step To in Phase of Algorithm and under the condition that approximation error S 1/CCTT)). with probability at least 1 - 6/2, regression oracle estimated wi satisfies E Bxwulff - f=( S C'd Fi/To, where i is the logarithmic term depending To, Ch. 2/5.
Lemma 6 is adapted from Lemma 5.1 of Liu & Wang 2023) to account for the additional approx- imation error from the distributed regression oracle. Specifically, instead of proving the risk bound for the exact minimizer úig. we consider wp that satisfies 1!,T, (wb) Lr (uig) ) I e for some con- stant As discussed in Section 4.1 this relaxation is essential for the communication efficiency in federated bandit optimization. And Lemma shows that, by ensuring S. (/(C"To) we can obtain the same regression oracle guarantee as in the centralized setting (Liu & Wang 2023). As discussed in Remark 4 this condition can be satisfied with O O( C' To llog( C"To)) number of iterations.
With Lemma 6 we can establish Lemma| below using the same arguments as Liu & Wang (2023).
Lemma (Regression oracle guarantee (Theorem 5.2 of Liu & Wang (2023) ). Under Assumption
and
3 and by setting S 1/(C"To). there exists an absolute constant C such that after time
step To in Phase I of Algorithm where To satisfies To 2 Cdd max 94/1--711 pe
10/12-7)
S), with
probability at least - 8/2, regression oracle estimated th satisfies 11000 w0113 <
Cd
MIu
5.2 PHASE II. CONFIDENCE SET CONSTRUCTION & OPTIMISTIC EXPLORATION
Confidence Set Construction In Phase II of Algorithm I each client selects its next point to evaluate based on OFU principle, which requires construction of the confidence set in equation The following lemma specifies the proper choice of Be,i, such that Ball,,,, contains true parameter w² for all E [T] with high probability.
Lemma 8. Under Assumption 1
2
& and by setting Se,s, θ (dm + dn d F=F//11 /12),,
To VNT, and X = NT, then [rr. w= 11 Il S Br.s. with probubility at least 1 6,
Vt [NT] Phase of Algorithm 7
Cumulative Regret in Phase II Thanks to the confidence sets established in Lemma 8 Algo- rithm [ can utlize a communication protocol similar to the ones designed for federated linear bandits Waan et al. 2020 Dubey & Pentland 2020) during Phase II. while providing much diverse model- ing choices. Therefore, our analysis of the communication regret and communication cost incurred in Phase II follows similar procedure its linear counterparts.
Denote the total number of global synchronizations (total number of times the event in line 6 of Algorithm| is true) over time horizon T as P [0, P). Then we use tp for p [P] to denote the time step when the p-th synchronization happens (define to = 0). and refer to the sequence of time steps in-between two consecutive synchronizations as epoch, i.e., the p-th epoch is (p--1 + 1, 1,4
7

---

Published as a conference paper at ICLR 2024
Similar to Wang et al. (2020); Dubey & Pentland (2020) Li & Wang 2022b). for the cumulative regret analysis in Phase II, we decompose P eppccs into good and bad epochs, and then analyze them separately. Specifically, consider imaginary centralized agent that has immediate access to each data point in the learning system, and we let this centralized agent executes the same model update rule and arm selection rule as in line 3-5 of Algorithm T
Then the covariance matrix maintained Va,, (wo) V Ss, (wo)) for [NT]. Then the p-th
by this agent can be defined as Dx Σ
dec(2
epoch is called good epoch if In det(2
S otherwise it is a bad epoch. Note that based NTC
on Lemma 9 we have In(det(ENT)) det(Al)) I du log (1
du := R. Since In( det(A))
deu(S) 2
In (et(Eng)
+ In( det(2in det(Exx)) In(
destEx)) R. and due to the pigeonhole principle, there det(A7)
det (2i,,)
can be at most Rt bad epochs. Then with standard optimistic argument (Abbasi-yadkori et al.
201
we can show that the cumulative regret incurred in good epochs Rgood = Ō VNTT) which matches the regret of centralized algorithm by (Liu & Wang 2023). Moreover, by design of the show that the cumulative regret - fp-+1111 I NN /V616NTT + ///
event-triggered communication in line 6 of Algorithm
incurred in any bad epoch p can be bounded by Dir
where NNT = O Fr
according to Lemma 8 Since there can be at most R bad epochs, the
cumulative regret incurred in bad epochs Road Ō(Ndw V
da F4
V7 + Nd L. By setting
communication threshold y = duF' we have Rnad = Ō Ō FVNT + SFNN
Combining
cumulative regret incurred during both good and bad epochs, we have
Rphuse Rgood + Read = =Ō Ö F+ /12 + N
Communication Cost in Phase II Consider some > 0. By pigeon-hole principle, there can be at most NTT epochs with length (total number of time steps) longer than a. Then we consider some epoch with less than time steps, similarly, denote the first time step of this epoch 4, and the last as le. i.e., la - Lg < a. Since the users appear in a round-robin manner, the number of interactions for any user E [A]] satisfies |Drad |Dr,,ll < N. Due to the event-triggered in line
6 of Algorithm 1. we have log det(2.,,)
dot.()...) 2N Using the pigeonhole principle again, we know that Ro
the number of epochs with less than time steps is at most synchronizations P
Therefore, the total number of 7N
NT
+
Ro 7N
1.
and the RHS can be minimized by choosing a = N /VT/R
so that P S 22/TR/y. With 7= du F²T a²N
P S 2 log(1+ (og(+++rcc//dd))) Ô( At
each global synchronization, Algorithm incurs (d + dww) communication cost to update the statistics. Therefore, Cphase 11 P. 2N d + d
6 EXPERIMENTS
In order to evaluate Fed-GO-UCB's empirical performance and validate our theoretical results in Theorem [5] we conducted experiments on both synthetic and real-world datasets. Due the space limit, here we only discuss the experiment setup and results on synthetic dataset. More discussions about the experiment setup and results on real-world datasets are presented in Appendix
For synthetic dataset, we consider two test functions, fi(x) = -t ai exp(- 25 Ax5(x; P)))) (see values of a, A, P in appendix) and f2(x) 0. cos(5)x;)) >i= x3. The de- cision set X' is finite (with |X' 50), and is generated by uniformly sampling from [0, and 1-1,10 1J8. respectively. We choose F to be a neural network with two linear layers, i.e., the model f(x) = W₂ (Wix + c1) + C22 where the parameters W1 E IR 25,d E R225 W2 E 25 02 IR, and o (2) = 1111+ eepp( (xx(())p))..)))))eee))))>>>>)))) Results (averaged over 10 runs) are reported in Figure 2 We included (Li and N-GO-UCB (Liu & Wang 2023) as baselines. One-GO-UCK learns model for all clients by immediately synchronizing every data point, and N-GO-UCB learns one model for each client with no communication. From Figure, 2 we can see that Fed-GO- UCB and One-GO-UCB have much smaller regret than other baseline algorithms, demonstrating
DisLinUCD WWag et al. 2020). Fed-GLB-UCB (Li & Wang 2022b),
et al. 2022a), One-GO-UCE
8

---

Published as a conference paper at ICLR 2024
Pvd-GLB-UICH
DeLintiC
Appredhikeewiitic
On-GO-UCC
N-G0AL
Ost
Ped-G0-L
Hartmann function Si (dæ
di
201,
100, N 20)
10a
Cumulative Regret
10a
Communication Cost
10²
10a
10*
500
1000
1500
2000
0
500
1000
1500
2000
Time
Time
Cosine8 function f2 (d2 8, dw
301,
100, N 20)
10a
Cumulative Regret
Communication Cost
10a
107
10a
10a
500
1000
1500
2000
500
1000
1500
2000
Time
Time
Figure Comparison of cumulative regret and communication cost on synthetic test functions.
the superiority of neural network approximation for the global non-linear optimization, though in- evitably this comes at the expense of higher communication cost due transferring statistics of size di 10 (compared with d ss 102 for the baselines). Nevertheless, we can see that the commu- nication cost of Fed-GO-UCB is significantly lower than One-GO-UCB and it grows at a sub-lincar rate over time, which conforms with our theoretical results in Theorem 5
CONCLUSIONS AND FUTURE WORK
Despite the potential of federated optimization in high-impact applications, such as, clinical trial optimization, hyperparameter tuning, and drug discovery. there gap between current theoretical studies and practical usages, i.e., federated optimization is often needed in online tasks, like next- word prediction on keyboard apps, but most existing works formulate it as an offline problem. To bridge this gap, some recent works propose study federated bandit optimization problem, but their objective functions are limited to simplistic classes, e.g., linear, generalized linear, or non parametric function class with bounded RKHS norm, which limits their potential in real-world upplications.
In this paper, we propose the first federated bandit optimization method, named ACd-GO-UCB, that works with generic non-linear objective functions. Under some mild conditions, we rigorously prove that Red-GO-UCB is able achieve Ō (VTTT) cumulative regret and ((N -55 commu- nication cost where T is time horizon and N is number of clients. Our technical analysis builds the distributed regression
upon Xu et (2018) 8): Liu Wang (203) and the main novelties oracle and individual confidence set construction, which makes collaborative exploration under fed- crated setting possible. addition, extensive empirical evaluations are performed to validate the effectiveness of algorithm, especially its ability in approximating nonlinear functions.
One interesting future direction is to generalize our work to heterogeneous clients, i.e., each client i e [N] has different reward function fi, that can be assumed to be close to each other in Dubey & Pentland (202I), or have shared components as in Li & Wang (2022a). This allows us to better model the complex situations in reality, especially when personalized decisions preferred.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
The work was partially supported by NSF Awards #2007117 and #2003257. The work was partially done when Chong Liu was at UCSB and when Chuanhao Li was at University of Virginia. We thank ICLR reviewers and the area chair for their valuable input that led improvements the paper.
REFERENCES
Yasin Abbasi-yadkori Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in Neural Information Processing Systems, 24, 2011.
Alekh Agarwal. Nan Jiang, Sham M. Kakade, and Wen Sun. Reinforcement learning: Theory and algorithms. 2021.
Zhongxiang Dai, Yao Shu, Arun Verma, Flint Xiaofeng Fan, Bryan Kian Hsiang Low, and Patrick Jaillet. Federated neural bandit, arXiv preprint (rXx::2205.14000 2022.
Yihan Du, Wei Chen, Yuko Yuroki, and Longbo Huang. Collaborative pure exploration in kernel bandit, arXiv preprint arXiv:2110.15771 2021.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. httttt/://archiv
ics. uci eddu/m /m]
Abhimanyu Dubey and Alex Pentland. Provably efficient cooperative multi-agent reinforcement learning with function approximation. arXiv preprint arXiv:2103.04972, 2021.
Abhimanyu Dubey and AlexSandy' Pentland. seitrenttiall--privatt federated linear bandits. Ad- vances Neural Information Processing Systems, 33, 2020.
David Eriksson, Michael Pearce, Jacob Gardner, Ryan D Turner, and Matthias Poloczek. Scalable global optimization via local bayesian optimization. Advances in neural information processing systems 32, 2019.
Sarah Filippi, Olivier Cappe, Aurélien Garivier, and Csaba Szepesvári. Parametric bandits: The generalized linear case. In Advances in Neural Information Processing Systems 23, 2010.
Dylan Foster and Alexander Rakhlin. Beyond ucb: Optimal and efficient contextual bandits with regression oracles. In International Conference on Machine Learning, 2020.
Peter Frazier. tutorial on bayesian optimization. arXiv preprint arXiv:1807.0288: 2018.
Peter Frazier and Jialei Wang. Bayesian optimization for materials design. In Information science for materials discovery and design, pp. 45-75. Springer, 2016.
Jemin George and Prudhvi Gurram. Distributed stochastic gradient descent with event-triggered the AAAI Conference on Artificial Intelligence, volume 34, pp.
communication. In Proceedings the 7169-7178, 2020.
Elad Hazan, Adam Klivans, and Yang Yuan. Hyperparameter optimization: spectral approach. In International Conference Learning Representations, 2018.
Jiafan He, Tianhao Wang, Yifei Min, and Quanquan Gu. simple and provably efficient algorithm
for asynchronous federated contextual linear bandits. arXiv preprint vrXiv:2207.03106, 2022.
Eshear Hillel, Zohar S Karnin, Tomer Koren, Ronny Lempel, and Oren Somekh. Distributed explo- ration in multi-armed bandits. Advances in Neural Information Processing Systems, 26, 2013.
Ruiquan Huang, Weiqiang Wu, Jing Yang, and Cong Shen. Federated linear contextual bandits. Advances in Neural Information Processing Systems, 34, 2021.
Donald R Jones, Matthias Schonlau, and William J Welch. Efficientt global optimization of expensive black-box functions. Journal of Global Optimization, 13(4):455-492 1998.
10

---

Published as a conference paper at ICLR 2024
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Advances and open problems in federated learning. arXiv preprint 1TX1::1912.04977, 2019.
Kirthevasan Kandasamy, Karun Raju Vysyaraju, Willie Neiswanger, Biswajit Paria, Christopher R. Collins, Jeff Schneider, Barnabas Poczos, and Eric P. Xing. Tuning hyperparameters without grad students: Scalable and robust bayesian optimisation with dragonfly. Journal of Machine Learning Research, 21(81):1-27, 2020.
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International Conference Machine Learning, 2020.
Solmaz S Kia, Jorge Cortés, and Sonia Martínez. Distributed convex optimization via continuous- time coordination algorithms with discrete-time communication. Automatica, 55:254-266 2015.
Nathan Korda, Balazs Szorenyi, and Shuai Li. Distributed clustering of linear bandits in peer to peer networks. In International Conference on Machine Learning, 2016.
Harold J Kushner. A new method of locating the maximum point of an arbitrary multipeak curve in the presence of noise. Journal of Basic Engineering, 8(1):97-106, 1964.
Chuanhao Li and Hongning Wang. Asynchronous upper confidence bound algorithms for federated linear bandits. International Conference on Artificial Intelligence and Statistics, 2022a.
Chuanhao Li and Hongning Wang. Communication efficient federated learning for generalized linear bandits. Advances in Neural Information Processing Systems, 35, 2022b.
Chuanhao Li, Huazheng Wang, Mengdi Wang, and Hongning Wang. Communication efficient dis- tributed learning for kernelized contextual bandits. Advances in Neural Information Processing Systems, 35, 2022a.
Chuanhao Li, Huazheng Wang, Mengdi Wang, and Hongning Wang. Learning kernelized contextual bandits in distributed and asynchronous environment. In The Eleventh International Conference on Learning Representations, 2022b.
Chuanhao Li, Huazheng Wang, Mengdi Wang, and Hongning Wang. Learning kernelized contextual bandits in distributed and asynchronous environment. In International Conference Learning Representations, 2023.
Lihong Li, Wei Chu, John Langford, and Robert E Schapire. A contextual-bandee approach to personalized news article recommendation. Proceedings of the 19th international conference on World wide web, pp. 661-670, 2010.
Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. On the convergence of fedavg on non-iid data. arXiv preprint 1rXivv1907.022166 2019a.
Yingkai Li, Yining Wang, and Yuan Zhou. Nearly minimax-optimal regret for linearly parameterized bandits. In Annual Conference Learning Theory, 2019b.
Chong Liu and Yu-Xiang Wang. Global optimization with parametric function approximation. In International Conference on Machine Learning, 2023.
Kanak Mahadik, Qingyun Wu, Shuai Li, and Amit Sabne. Fast distributed bandits for online recom- mendation systems. In Proceedings of the 34th ACM international conference on supercomputing. pp. 1-13, 2020.
Brendan McMahan, Fider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-effiiies learning of deep networks from decentralized data. In International Conference Artificial Intelligence and Statistics, 2017.
Aritra Mitra, Rayana Jaafar, George J Pappas, and Hamed Hassani. Achieving linear convergence in federated learning under objective and systems heterogeneity. arXiv preprint arXiv:2102.07053. 2021.
11

---

Published as a conference paper at ICLR 2024
Nathan Nakamura, Jason Seepaul, Joseph B Kadane, and B Reeja-Jayan. Design for low- temperature microwave-assiscen assiisee crystallization of ceramic thin films. Applied Stochastic Models in Business and Industry, 33(3):314-3211 2017. 2017.
Reese Pathak and Martin J Wainwright. Fedsplit: an algorithmic framework for fast federated optimization. Advances in Neural Information Processing Systems, 33:7057-7066, 2020.
Maxim Raginsky, Alexander Rakhlin, and Matus Telgarsky. Non-convex learning via stochastic gradient langevin dynamics: nonasymptotic analysis. In Conference on Learning Theory, pp- 1674-1703, PMLR, 2017.
Johannes Schmidt-Hieber.
Nonparametric regression using deep neural networks with relu activation function. Annals of Statistics, 48(4))1875-1899) 2020.
Bobak Shahriari, Kevin Swersky, Ziyu Wang, Ryan P Adams, and Nando De Freitas. Taking the human out of the loop: A review of bayesian optimization. Proceedings of the IEEE, 104(1): 148-175, 2015.
Weiwei Shen, Jun Wang, Yu-Gang Jiang, and Hongyuan Zha. Portfolio choices with orthogonal bandit learning. Twenty-fourth international joint conference on artificial intelligence, 2015.
Niranjan Srinivas, Andreas Krause, Sham Kakade, and Matthias Seeger. Gaussian process opti- mization in the bandit setting: regret and experimental design. In International Conference Machine Learning, 2010.
Chao Tao, Qin Zhang, and Yuan Zhou Collaborative learning with limited interaction: Tight bounds for distributed exploration in multi-armed bandits. In Anmual Symposium on Foundations of Com- puter Science, 2019.
Soffa S Villar, Jack Bowden, and James Wason. Multi-armed bandit models for the optimal design of clinical trials: benefits and challenges. Statistical science: a review journal of the Institute of Mathematical Staristics, 30(2):199, 2015.
Yuanhao Wang, Jiachen Hu, Xiaoyu Chen, and Liwei Wang. Distributed bandit learning: Near- optimal regret with efficient communication. In International Conference on Learning Represen- tations, 2020.
Pan Xu, Jinghui Chen, Difan Zou, and Quanquan Gu. Global convergence of langevin dynam- ics based algorithms for nonconvex optimization. Advances in Neural Information Processing Systems, 31, 2018.
Qiang Yang, Yang Liu, Tianjian Chen, and Yongxin Tong. Federated machine learning: Concept and applications. ACM Transactions on Intelligent Systems and Technology, 10(2):1-19, 2019.
Xinlei Yi, Lisha Yao, Tao Yang, Jemin George, and Karl H Johansson. Distributed optimization for second-order multi-agent systems with dynamic event-triggered communication. In 2018 IEEE Conference on Decision and Control (CDC), pp. 3397-3402. IEEE, 2018.
Yuchen Zhang, Percy Liang, and Moses Charikar. A hitting time analysis of stochastic gradient langevin dynamics. In Conference on Learning Theory, pp. 1980-2022. PMLR, 2017.
12

---

Published as a conference paper at ICLR 2024
A
NOTATION TABLE
Table I: Symbols and notations.
Symbol
Definition
Description
[Allop
operator norm of matrix A
Ball,
equation given in Lemma
parameter uncertainty region at round /
Br
parameter uncertainty region radius at round
C,S
constants
dz
domain dimension
dw
parameter dimension
5
failure probability
covering number discretization distance
7
o-sub-Gaussian
observation noise
(x) x
objective function at x parameterized by w objective function at w parameterized by x 1st order derivative w.r.t. w parameterized by x 2nd order derivative w.r.t. parameterized by x function range constant bound
[x(w)
Vfx(w)
4 (w)
", 1"
logarithmic terms
L(w)
(f(((W) fo(w")
E
expected loss function
regularization parameter
1
strong convexity parameter
11,2..., T
integer set of size T
N
number of agents
Oracle
regression oracle
number of iterations to execute Oracle
approximation error guaranteed of Oracle communication threshold
F1
Jw (x*)
fw (Tt
instantaneous regret at round cumulative regret after round covariance matrix at round & time horizon in Phase time horizon Phase II
RT
Σ
equation
To
uniform distribution
w
w E W
function parameter
w
w² E W
truc parameter
oracle-estimated parameter after Phase updated parameter of client i at round t
equation
W
W C [0,
parameter space data point
x E
x*
optimal data point Ep norm
|x] 1p
x
vx x
Ax
distance defined by square matrix A function domain
X
X C
Rdz
y
F.F
function range
13

---

Published as a conference paper at ICLR 2024
B ADDITIONAL DISCUSSIONS
B.1 MORE DETAILS ON RELATED WORKS
Ma- hadik et al., 2020 Wang et al., 2020, Dubey & Pentland 2020 Huang et al. 202 designing an efficient communication strategy is the main focus. Existing algorithms mainly differ in the relations of learning problems solved by the clients (i.e., identical vs.. clustered) and the type of communi- cation network (i.e., peer-to-peer (P2P) vs., star-shaped). Kordaa et al. (2016) studied two problem settings with P2P communication network: 1) all the clients solve common linear bandit prob- lem, and 2) the problems are clustered. Mahadik et al. (2020) later proposed an improved algorithm on the second problem setting studied by Korda et al. (2016). However, both works only tried to reduce per-round communication, and thus the communication cost is still linear over time. Two follow-up studies considered the setting where all clients solve common linear bandit problem with time-aryying arm set and interact with the environment in round-robin fashion (Wang et al.) 2020 Dubey & Pentland 2020). Similar our work, they also used event-triggered communica- tions to obtain a sub-linear communication cost over time. In particular, [Wan et al. (2020) con- sidered star-shaped network and proposed synchronous communication protocol for all clients to exchange their sufficient statistics via the central server. [Dubey & Pentland (2020) extended this synchronous protocol to differentially private LinUCB algorithms under both star-shaped and P2P network. (Huang et al. (2021) considered a similar setting but with fixed arm set and thus proposed a phase-based elimination algorithm. Later, in order to improve robustness against possible strag- glers in the system, Li & Wang (0022)); He et al. (2022) proposed asynchronous communication protocols for the federated linear bandit problems. All the works mentioned above consider linear models, where efficient communication is enabled via closed-fome model update. The only existing work that studies nonlinear models with iterative optimization is by Li & Wang (2022b), who em- ployed combination of online and offline regression, with online regression adjusting each client's local model using its newly collected data, and offline (distributed) regression that conducts iterative gradient aggregation over all clients for joint model estimation during global synchronizations.
More details on distributed//eddrraee bandits For distributed bandits (Korda et al. 2016
Offline federated learning Another related line of research is federated learning or decentralized machine learning that considers offline supervised learning scenarios (Kairouz al. 2019). FedAvg (McMahan et al. (017]) has been the most popular algorithm for offlin federated learning. How- ever, despite its popularity, several works (Li et al. 2019a Karimireddy et al.) 2020 Mitra et al. 2021) identified that FedAvg suffers from a client-drift problem when the clients' data are non-IlI (which an important signature of our case), i.e., local iterates in each client drift towards their local minimum. This leads to sub-optimal convergence rate of FedAvg, i.e., sub-linear conver- gence rate for strongly convex and smooth losses, though a linear convergence rate is expected in this case. To address this, Pathak & Wainwright (2020) proposed an operator splitting procedure to guarantee linear convergence to a neighborhood of the global minimum. Later, MMtra et al.) (2021) introduced variance reduction techniques to guarantee exact linear convergence the global mini- mum. However, due to the fundamental difference in the learning objectives, they are not suitable for our federated optimization problem: their focus is collaboratively learn good point estimate over fixed dataset, i.e., convergence to the minimizer with fewer iterations, while federated bandit learning requires collaborative confidence set estimation for efficient regret reduction. This is also reflected by the difference in the design of communication triggering events. For decentralized su- pervised machine learning, triggering event measuring the change in the learned parameters suffices (Kia al., 2015; Yi et al. 2018; George & Gurram 2020), while for federated bandit learning, triggering event needs to measure change in the volume of the confidence set, i.., uncertainty in the problem space (Wang al. 2020 Li & Wang 2022a)
B.2 SUMMARY OF EXISTING FEDERATED BANDIT ALGORITHMS
Here we provide a summary of existing works in federated bandit optimization in Table 2 which mainly differs in their modeling assumptions, type of communication protocol (synchronous vs asynchronous), as well as theoretical guarantees on regret and communication cost (in terms of N and 7).
14

---

Published as a conference paper at ICLR 2024
Table 2: Summary of existing federated bandit algorithms.
Related Works
Modeling Assumption
Protocol
Regret
Communication
Wang al.
2020
linear
synchronous
VNT
N
Li & Wang 2022a
linear
asynchronous
VNT
N
He et al.
2022)
linear
asynchronous
NT N
N
Li & Wang
(0022b)
generalized linear
synchronous
VNT
N
Li al.
2022a)
kernel
synchronous
VNT
N2
Li al.
2022b
kernel
asynchronous
NT -N
N
Dai
(2022
kernel (NTK)
synchronous
NVT
51.222
Ours
nonconvex
synchronous
VNT
N VT
C AUXILIARY LEMMAS
Lemma (Lemma C.5 Liu & Wang & 3 hold. Then
2023
Set Ee,is as in equation 6 hnd suppose Assumptions
det 1i
De.se
In
< dhu In 1
det Eo
duu
Lemma 10 (Lemma C.6 of Liu & Wang 2023 ) Set Er,i, as in equation Fand suppose Assumplions & 3 hold. Then
Ex Σt-1.i
Vzz, (wo)
Eー Eg- Via, 21n
En
DED
Lemma 11 (Seff-normalized bound for vector-valued martingales (Abbasi- (Abbasi-yadkon et al. 2011 Agarwal al. 2021I). Let {m)) be a real-valued stochastic process with corresponding filtra- lion [Fi] ii such that y is F; measurable, R[na[Fi-1] = 0, and iJs is conditionalyy r-sub-Gaauste with RR. Let 2 be a stochastic process with X; E (some Hilbert space) and X; being F; measurable. Assume that a linear operator Σ - H is positive definite, i.e., x Ex > for any H. For any t, define the linear operator Σ, Eg + 1 X;X, (here x denotes outer-product in H)) With probability at least 5, we have for all 1 1:
/et((i.) det(2o)
Σ X
S <²2 202n In
Lemma 12 (Risk Bounds for e-approximation of ERM Estimator). Given dataset {I,, Uo Ma where ys is generated from equation 7 and f is the underlying true function. Let fr be ERM estimator taking values in F where F is finite set and F C {f [0, 1] - I-F,, F|} for some F denotes its c-approximation. Then with probability at least 1 - 5, satisfies that
F F21, 1.
B[( - -[))--Jo'}} 1 a
inf B[(S fu) JEF
F2 (2 2ln(2/6)
+ 1 1-a
6
to
to
for all (0, and 0.
Proof of Lemma 12
Define the risk and empirical risk function
R()) = Ex,y [[(X) - y)
1
R(f) = t ==1
Σ (f(x.) - y2)2.
By definition,
/ = - = x) = arg min R()).
fer
15

---

Published as a conference paper at ICLR 2024
Denote the excess risk and the empirical excess risk
8()) = R()) - R((*),
ε(f) R(f) R(f)).
Following the same steps in Nowak [2007], we have
1n - a)-a E(f)+ c() In In 1/8 R(f)) R(f*)+ 2 11) at
at
where penalties cl are positive numbers assigned to each f E F that satisfies Σ 2- < 1. We set to F2 In( according Lemma (Shmiidttt Hieberr 2020). Now recall that, have denoted fe as the ERM estimator, i.e., fo arg min seF R(f), and ft as its e-approximation, such that
R(fa) R(Fi)= SC
Therefore, have
F (n(FF) In + In 1/6
(1 - ( s +
at
I' FF
In + In 1/6
<((f) +
te
at
F [n In2 In 1/8
<(((T)
t
Due to Sraig-Bernstein inequality, we have
In 1/8 at
+ + +
Combining the two inequalities above, we have
8(f) S 1 + a E(ft) 1 1 at
1 F2
1/8
c.
1-a
D COMPLETE PROOFS
D.1 PROOF OF LEMMA 6
Proof of Lemma 0 The regression oracle lemma establishes on Lemma 12 which works only for finite function class. order to work with our continuous parameter class W, we need E-covering number argument. First, let w. denote the e-approximation of ERM parameter and finite pa- rameter class after applying covering number argument on W. By Lemma 12 we find that with probability at least 1 - 5/2,
+ a
Exsul(f((w) - ff((")))] F2 In F2I((W) (22)))
inf Ez-ul(fo(te - (z(ww)) v - a weWu(w"))
Toa
2 ln(4/))
1 +
Toa
1 + 0 F2 In In(())
2 21n(4/8) Toa
Toa
1
where the second inequality is due to Assumption Our parameter class W C [0, 10w, so In((vi/)) In(1/edw) d, ln(ee) and the new upper bound is that with probability at least - 8/2,
dew In(E/E) F2m(/e
ln(2/8) To
E Ex-ul (fa(() - fa(w*))²] cr(dut
+
To
16

---

Published as a conference paper at ICLR 2024
where C" is universal constant obtained by choosing = 1/2.. Note úi is the parameter in W after
discretization, not our target parameter th E W. By (a + Σ 2a² + 26
Ez~ul(fa fa(w*)) - 2E, 2E (lf (wo) f= 2E
((fz((()) 2E
f=(("))²
S C 20 dw F2 ln(1/E) (2/0)) E)
To
To
where the second line applies Lemma 12 L and 1/(2 get
discretization enror E, and Assumption By choosing
(18) To + C" F² In + 20" ln(2/))
I C² dn (n(T,C)) + ln(2/8)
To
To
To The proof completes by
where can take C" 2C" (assuming 2 dey (og(T)C))).
defining as the logarithmic term depending on To, 2/6.
D.2 CONFIDENCE ANALYSIS
Lemma 13 (Restatement of Lemma
Set Wes Et,i, as in eq. equation
6 equation 5
Set St,s, as
Brss θ dioop + 1 Eap
122
Suppose Assumptions
12
hold and choose To VNT CXVNT. Then VI [NT] in w w1,..... Br with probability at least -. 6.
Phase II of Algorithm 7 We,k
Proof. The proof has two steps. First we obtain the closed form solution wt. Next we prove the upper bound of [| w=Il Il..., matches our choice of 3e,5
Step 1: Closed form solution of wt,i, Let V denote V Vx, (wo) in this proof.
Recall Wy,4 estimated by solving the following optimization problem:
W2,5.
=- biie br.i. + A w
arg min
X
w|w woll +
1
Σ
- (ww-úo)) + Sx, (100) y=)²
a 2
sED,(i.)
The optimal criterion for the objective function is
0 = A(wr, - wo) +
Σ
((Wr. - - T + (w0) - V.
(ED.(ts
Rearrange the equation and we have
X(We.s. - -10) +
(wr,, - wo) T VV= =
Σ
(ys - (wo))
+ED)(t)
(EDr(h)
X(We,
1o) Σ
wp) TVV
Σ
(Us fx.(w") + fxx (w²) -fx. (1o))
xEDr(te)
(ED)
X(Rirji -wo) +
W
VV
Σ
V + ml + (x,(()) - -Sx, (1)))),
(E))
(EDi(1)
W
AI Σ
V
Xwnn = Σ
(w0
V
+ 17s + (w²) - Sxx (wo))),
(ED
(ED
1 E1,, X1o
(w) V + 17 + fx. - fxx (wo))),
sED,(1)
17

---

Published as a conference paper at ICLR 2024
where the second line is by removing and adding back fz, (w*), the third line is due definition of observation noise ? and the last line is by our choice of Σt,s, (eq. equation 6). Now we have the closed form solution of i,,e
A2 1,0 Tp
Σ sEDi(à)
(w 1 V + 7 + Sx. (w*) fx, (w)))
where V denotes V fx, (100). Then tr
w" can be written as
Wr - -w" = 5-1
Σ (EDi(A))
6p + + (w=) - fx. (wo)) V(V
+ - 10
-i De.i. w
21,i
-
Σ (EE)((t)
V(V
Tp + Te + fx. (w²) - fx. (100)
+ AM (100 - w²)
Σ
VV
(ED((E))
x-1 (ED((A)
(Bgg w²) + 17s fx,(w") fx. (1o0))
+ +AEr, (100 w²)
Σ (ED)(A)
I10i w0 11:= (0))
+ Ezg
Vna
1 (m0 -w*),
(ED)
(8)
where the second line is again by our choice of E, and the last equation is by the second order Taylor's theorem of [x, (w") úh where き lies between w² and wo.
Step 2: Upper bound of || - w w Multiply both sides of eq. equation & by D and we have
Ete (104, - ww)
=
Σ (ED.(t.)
Vxx. (wo)
-w" "''1>> (18)
2 t
+ 1
Σ
(w0))
+xE, (100 - w*).
(ED,(is)
Take square of both sides and by inequality (a +
c)² 4a²
462 4c² we obtain
| w= 1...... I
Σ xEDi(is
Vx, (wo))
+ 4221 w 11
Σ
Vx. (wo) - w0 11 fx, (1))
(E)
The remaining job is bound three terms in eq. equation 4 equation 9 can be bounded as
individually.
The first term of eq.
det (E,s, dot(Ex)
Σ (1))
Sx, (wo)
< 4o 2 log
87
Exh
iC2 d
222
< 2
di log
1
+ log
35
< 0
18

---

Published as a conference paper at ICLR 2024
where the second inequality is due to self- ceff-normalized bound for vector-valued martingales (Lemma
I in Appendix ( and Lemma| 7 the second inequality is by Lemma 9 and our choice of
36/ ( and the last inequality is by defining z' the logarithmic term depending on i, d,d., Cg. / 2/6 (with probability > 1 - 6/2). The choice of 6 guarantees the total failure prob-
ability over rounds is no larger than 8/2.
Using Lemma 7 the second term in eq. equation 9 is bounded as
4XCd F2
4 w² 1
"I
PTo
Again using Lemma and Assumption 3. the third term of eq. equation 9 can be bounded as
Vxx (100)1100 w0 ( (x, (w)
(E))
CCndun F2, uToo
fxx, (20p)
(EDi(a)
C. F28 12T8
Σ (ED)(E)
V Vxx (10b)
E0-1
C 12T8
Σ (E))(G)
Vxx, (100)
ET.t
('e)(
Rearrange the summation and we can write
T Σ (xx
CORREA 12T8
V Sx (1)))
(ED)
s'ED((ie)
V (wo) T Enghh V Vxx, (10)
12T8
(b) (1))
CCC F22
Σ
Σ
|V (100
/ V (100))
12Tz
(6) (i))
C'C. F4, 12T9
Σ
|V (w0) (wD))
Σ
V (100
(ED,(L)
('ED.(E))
COORE
Σ
| (wo) (wo))
1PT3
(EDi(()
CR F42 1213
Σ
Σ (ED.(A)
V.. (t0v)) 1
sED.(6)
& F4tii ,2
1P13
where the second last inequality is due to Cauchy-Schward inequality and the last inequality is by Lemma 10
19

---

Published as a conference paper at ICLR 2024
Finally, put three bounds together and we have
F2
CC p2T
| w. "11l I 4d
pTo
0o 50(d002
duF2
12NT
where the last inequality is by our choices of X = -AVNT, To VNT. Therefore, our choice of
Be, = (dmno²
1
122
J
guarantees that w" is always contained in Ball, with probability 1 1
D.3 CUMULATIVE REGRET AND COMMUNICATION COST IN PHASE II
Cumulative Regret in Phase II Thanks to the confidence set established in Lemma g Phase II of Algorithm can operate in a similar way existing works federated linear bandits (Wang et al. 2020, Dubey & Pentland] 2020), while allowing for a much wider choices of models. The main difference is that, the regret of their work depends on the matrix constructed using context vectors x, for s = 1...... for the selected points, while ours rely on the matrix constructed using gradients' w.r.t. shared model thp. the following paragraphs, we first establish the relation between instantaneous regret Ty and matrix E,-1, and then analyze the regret of Algorithm [
Though, compared with Liu & Wang (023). we are using a different way of constructing the con- fidence ellipsoid, which is given Lemma Their Lemma 5.4, which is given below, still holds, because only requires Ball;-1.4, to be a valid confidence set, and that Assumption 2 holds.
Lemma 14 (Instantaneous regret bound [Lemma 5.4 of Liu & Wang 2023 ). Under the same condition as Lemma 8 in Phase II of Algorithm for all E [NT], we have
ri n S 1 Vxx 11
2Br,CCh/AA
with probability at least 1 5.
Denote the total number of global synchronizations (total number of times the event in line 6 of Algorithm is true) over time horizon as P E N.. Then we use tp for E [P] to denote the time step when the p-th synchronization happens (define to 0), and refer the sequence of time steps in-between two consecutive synchronizations as an epoch, i.e., the p-th epoch is ft--1 + 1, tp]- Similar to Wang et al. (2020); Dubey & Pentland (2020); Li & Wang (2022b), for the cumulative regret analysis in Phase II, we decompose P epochs into good and bad epochs, and then analyze them separately.
Specifically, consider an imaginary centralized agent that has immediate access to each data point in the learning system, and we let this centralized agent executes the same model update rule and arm selection rule as in line 3-5 of Algorithm [ Then the covariance matrix maintained by this agent for [NT]. The p-th epoch is called good can be defined as Σ, = Ei= Vfn,, (wo) V (1,0)
epoch if
det(Eep) det (Epp.))
In
< 1,
otherwise it is a bad epoch. Note that based on Lemma g we have In(det(Ent)/ det S due log (1 + NTC2 = R. Since In det(Ee,) d R. and due the pigeonhole principle, there can be at most R bad epochs.
det(A/) +I dct(S..,) ++...+Inn det(Ex
det(Eop) = In dot(Ew))
det(S..)
det(Xi)
20

---

Published as a conference paper at ICLR 2024
Now consider some good epoch p. By definition, we have det(Se--1) det(2x-7,44)
det(E
S e, for any
det dct(Sipp-1)
I 1p- + 1, (,). Therefore, the instantaneous regret ry is incurred during a good epoch, we have r1 S 2 3
23 23,-1,1, Ch
(wo))l +
28: 1,1, Ch
s 22 B, 1, V (mb))
V Sz, (wo) (000)>==),,
X
del(Er-1)
- Ch
= 22 1,
1.6 V Sa,
(wo) (wo))
det dct(Ex-1,5)) 11-1,5))
x
23,-1,44 Ch.
22 1, Va. (0) (0)01l??
A
where the first inequality is due to Lemma 14 epoch, i.e., det(Ir-1) < det(Etp-)) Se.
and the last inequality is due to the definition of good
det(
det(E..)..,)
This suggests the instantaneous regret incurred in good epoch is at most ve times of that incurred by the imaginary centralized agent that runs GO-UCB algorithm of Liu & Wang (2023).
Therefore, the cumulative regret incurred in good epochs of Phase II, denoted Rgood
P 1(m p=1
(et,),,)) det(Iep-1)
Pp
NT
NT
Rgood
Σ
11
S
r
S
NT
t=tp-1
1=1
NTC2
852
CANT
S v NT
16
In(1 +
9
y
X2
where the last inequality due to (a+ < 2a +b2 Lemma 9 and Lemma
10
Note that 9NT
O Frr according to Lemma By setting
Cx CNVNT, we have Rgood
Ō
d F
/NT
Consider some bad epoch p, we can upper bound the cumulative regret incurred by all N clients in this epoch p as
N
Σ
Σ
N
Σ
/V (100))
23 1.5e C
X
LE DeDepiiiey 1
(Deipll 1Dpp...1)83N7
Σ
(200)11 +887
D7.1.0
BED AD
163NTY C
where the first inequality is due to Lemma 14 the second is due to Cauchy-Schwand inequality and (a + 6)2 < 2a² 262, and the last is due to Lemma 10 and event-trigger with threshold y in line of Algorithm|] 0
NTC2 dex
Since there can be at most R = duo log (1 +
bad epochs, the cumulative regret incurred in
bad epochs of Phase II, denoted as Rbad is Ö dw V
de F
+ Nd d pd n ). By setting commu-
nication threshold 7 = ds FTT we have Ront = Ō L
VNT
F d
Combining cumulative
N²
#²
regret incurred during both good and bad epochs, we have
(
d3 pa
d 1
Rphuse II Rgood Phoad Ô
VNT
N
122
Communication Cost in Phase II Consider some 0. By pigeon-hole principle, there can be at most [TT] epochs with length (total number of time steps) longer than a. Then consider some epoch with less than time steps. We denote the first time step of this epoch 4, and
21

---

Published as a conference paper at ICLR 2024
the last fe. i.e., tg Since the users appear in round-robin manner, the number of interactions for any user E [N] satisfies D - Di., < N Due to the event-triggered line of Algorithm Il we have log det(Es,,)
det(E
Using the pigeonhole principle again, we know that Therefore, the total number of and the RHS can be minimized by choosing N /TT/// 7/
the number of epochs with less than time steps is at most synchronizations P 1
Ro 7X
Ra
Ö(VNN2/F)) At each global synchronization, Algorithm incurs (N - + dw) communication cost to update the statistics. Therefore, Ophuse P (d + d
so that P S 2 With 7 d ='N
P 2 N +oo((++NTg//ddd
F
&N F22)
E EXPERIMENT SETUP & ADDITIONAL RESULTS
Synthetic dataset experiment setup Here we provide more details about the experiment setup on Specifically, we compared all the algorithms the following two
synthetic dataset in Section 6 synthetic functions
f1(x) = Σ
ā exp(
Σ j=1
Ax Pr))))
i=1
8
f2(x) 0.1
Σ
Σ x?.
Both are popular synthetic functions for Bayesian optimization benchmarking function fi is called Hartmann function, where
The 6-dimensional
10, 3, 17,3 0.05, 10, 17, 0.1,8, 14 10, 17,8, 0.05, 10, 0.1,
1
1312, 1696, 5569, 124, 8283, 5886
2329, 4135, 8307, 3736, 1004, 9991
31.003..3 A=
P
2348,
2883, 3047, 6650
4047, 8828, 8732, 5743, 1091, 381
And the 8-dimensional function fe is a cosine mixture test function, which named Cosine8. To be compatible with the discrete candidate set setting assumed in prior works (Wang et al. 20200] [i & Wang, 2022b Li et al. 2022a), we generate the decision set for the optimization of by uniformly sampling 50 data points from [0. 1]6 and similarly for the optimization of fz. 50 data points from [-1, _ Following our problem formulation in Section 3 at each time step f E [T'] (we set set 7' = 100), each client i E [N] (we set N 20) picks data point Tt, from the candidate set X. and then observes reward yt, generated by function f1, f2 as mentioned above. Note that the values negated, so by maximizing reward, the algorithms are trying to find data point that minimizes the function values. We should also note that the communication cost presented in the experiment results defined the total number of scalars transferred in the system (Wang et al. 2020), instead of number of time communication happens (Li & Wang 2022a).
of both functions
Real-world dataset experiment setup results To further evaluate GO--GO-UCB's performance in more challenging and practical scenario, performed experiments using real-world datasets: MagicTelescope and Shuttle from the UCI Machine Learning Repository (Dua Graff 2017). We prepprocessed these two datasets following the steps in prior works (Filippi et al.) 2010), by
partitioning the dataset in 20 clusters, and using the centroid of each cluster as feature vector for the arm and its averaged response problem introduced Section 3 with T = 100 and N = 100. From Figure 3 we can see that Fed-GO-UCE outperforms the baselines, with relatively low communication cost.
reward. Then simulated the federated bandit learning
We chose them from the test functions available in BoTorch package. See httpp::/bbtorcch.org api/ htt//est_fuumee funct ons. html for more details.
22

---

Published as a conference paper at ICLR 2024
Fed-GLB-UCB
DoLiaUC
AppreaDueeraiUCC
One-CO-CCB
N-GOECE
Ous-LiaUCB
F.d.CO-L'CB
Magic Telescope (d,, 10, dw = 201, T 100, N 100)
10
Cumulative Regret
Communication Cost
10a
10P
10
107
2000
4000
6000
8000
10000
6000
8000
10000
Time
Time
Shuttle (d, 10, dn
201,
100, 100)
10
Cumulative Regret
10a
Communication Cost
10a
10a
2000
4000
6000
8000
10000
0
2000
4000
6000
8000
10000
Time
Time
Figure 3: Comparison of cumulative regret and communication cost on real-world datasets.
23


Reviews:
[{"review_id": "TNrNKxCf0Q", "reviewer": "Reviewer_rFun", "summary": "This paper's primary focus is on tackling the non-linear bandit optimization problem within a federated setting. It introduces the innovative Fed-GO-UCB algorithm, which represents a substantial improvement over previous centralized algorithms. Remarkably, this federated algorithm achieves a theoretical regret guarantee comparable to previous centralized approaches, specifically $O(\\sqrt{NT})$, while also demonstrating sub-linear communication complexity. Additionally, the empirical results robustly confirm the efficiency and effectiveness of the proposed algorithm.", "questions": "1. In the Fed-GO-UCB algorithm, it's important to clarify that agents should reset $\\Delta\\Sigma$ and $\\Delta b$ to zero after uploading their respective datasets.\n\n2. In Figure 3, the observation that the communication complexity for several algorithms does not start from zero at time $T=0$ can be puzzling. It would be beneficial if the author could offer an explanation for this behavior.\n\n3. For the Theorem 5, is it possible to provide a corresponding lower bound to suggest that $\\Omega(\\sqrt{T})$ communication is necessary. For instance, Min el al., 2023 [1] provide a lower bound showing\nthat a minimal $\\Omega(dM)$ communication complexity is required to improve the performance of linear bandit (or MDPs) through\ncollaboration. Insights into lower communication complexity bounds would strengthen the support for the Fed-GO-UCB algorithm and provide a more comprehensive understanding\n\n[1] Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximation", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The proposed algorithm excels in providing a near-optimal guarantee for federated learning with generic non-linear function optimization.\n\n2. The empirical results robustly confirm the efficiency and effectiveness of the proposed algorithm.\n\n3. This paper is well-written and easily comprehensible.", "weaknesses": "1. The theoretical guarantee of Fed-GO-UCB relies on several critical assumptions (Assumptions 1 to 3), and it may be challenging to establish whether these assumptions hold in common situations, such as neural networks with ReLU activation functions. Even if the assumptions hold, determining the values of the parameters in Fed-GO-UCB that depend on these assumptions can be a non-trivial task. It remains an open question how to calculate these constants and set the algorithm's parameters effectively in practical applications.\n\n2. The communication complexity, as indicated by Theorem 5, is stated as $O(\\sqrt{T})$, which is significantly higher than the communication complexity of $O(\\log T)$ achieved by previous works. Presenting this level of communication cost as efficient without providing lower bound results for communication complexity can be misleading. Furthermore, the experimental results in Figure 2 show a communication complexity of $10^7$ for round $T=500$, which seems highly inefficient in practice.\n\n3. In the context of federated learning, there is often a tradeoff between communication complexity and performance, specifically in terms of regret guarantee. It's a common observation that algorithms with higher communication complexity can potentially achieve better performance. To gain a clearer understanding of the algorithms' relative performances, it would be beneficial for the author to conduct experiments where the selected parameters makes different algorithms have similar communication complexity. This approach would enable a direct and fair comparison that isolates the impact of communication complexity from the approximation capabilities, providing more conclusive insights into the algorithm's efficiency and effectiveness in a practical federated learning setting.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wXNdm7Fll1", "reviewer": "Reviewer_emcJ", "summary": "This paper presents a communication-efficient federated algorithm, Fed-GO-UCB, for a bandit optimization problem with non-linear function. Their analysis shows that the regret upper bound of Fed-GO-UCB matches that of Fed-GO-UCB's centralized counterpart with sub-linear communication costs. The authors explain the main logics behind analysis in details. Empirical experiment results are also included.", "questions": "- The novel technical contributions of this work are Lemma 6 and 8 if I understand correctly. Shouldn't these two lemmas be named as Propositions instead? \n- Could the authors comment on the difficulties in obtaining Lemma 6 and 8? Which part of difficulties is due to the federated setting and which part of the difficulties is due to the non-linear function?\n- Could the authors comment on the tightness of the communication cost bound?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- This work is one of the pioneering effort in studying federated bandit optimization with non-linear function\n- This work generalizes a distributed regression theoretical guarantee to account for approximation error, which may be of interest to the federated learning community \n- This paper is in general well written and easy to follow", "weaknesses": "- The literature review provided is somewhat brief and limited in scope and detail\n- Though this work features considering non-linear function optimization, it seems that its main contribution is on addressing the challenges of federated setting. Could the authors discuss more about the special challenges of non-linear function optimization?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jsqY3W40sb", "reviewer": "Reviewer_yBxF", "summary": "This paper studies the federated bandit optimization where the objective functions are non-linear yet i.i.d across $N$ agents. Existing works focus on either simplistic function classes or non-parametric function classes with bounded RKHS norms. In this paper, the authors propose a new Fed-GO-UCB algorithm, which contains two phases: the uniform exploration phase and the online learning phase. The authors prove that Fed-GO-UCB ahives $O(\\sqrt{NT})$ regret while achieving $O(N^{1.5}\\sqrt{T})$ communication cost. Finally, the authors conduct empirical experiments on both synthetic and real-world data to validate their theoretical results.", "questions": "Please justify or comment on the three weaknesses above.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The problem setting is new and well-motivated. Compared with existing works that follow either simplistic function classes or non-parametric function classes with bounded RKHS norm, this work considers a more general non-linear form of objective function.\n2. The results are sound and complete, with both theoretical analysis and empirical evaluation.\n3. The algorithms and the analysis both have some novelty, for example, the two phase algorithms and the analysis built upon it.", "weaknesses": "1. Novelty: Though the setting is new and the two-phase design is interesting, after the uniform exploration (phase 1), it seems to me that one can combine the techniques from centralized non-linear bandit optimization problem with the communication protocol from the federated linear bandits (Li & Wang, 2022a) and federated generalized linear bandits (Li & Wang, 2022b).\n2. Comparison with federated generalized linear bandits (Li & Wang, 2022b): From the algorithmic perspective, Li & Wang 2022b also uses some global updates (similar to uniform exploration) after the communication condition (line 6 of Algorithm 1) is satisfied, I am wondering if the current paper also uses this way to update $\\hat{w}_0$, will there be any difference or improvement in the regret analysis? Moreover, I find that Li & Wang, 2022b can only achieve $O(dN^2\\sqrt{T})$ communication. Since I suppose the current paper is more general and can cover Li & Wang 2022b, does this mean that the current paper can achieve a $O(\\sqrt{N})$ improvement because of the difference in the algorithm design?  \n3. Lower bound: I do not find any discussion about the lower bound result or any discussion about it. Without it, one cannot see how tight the results are in terms of $$N, T$$ and all other parameters. I hope the authors can discuss the tightness of their results during the rebuttal.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9lTtI9qB9t", "reviewer": "Reviewer_6154", "summary": "The paper introduces Fed-GO-UCB, a federated bandit optimization algorithm designed for generic non-linear objective functions, addressing the limitations of existing methods that are confined to simplistic function classes. Federated optimization enables collaborative model estimation across decentralized datasets, ensuring data privacy and allowing large-scale computing. This is particularly beneficial for tasks requiring online interactions, such as next-word prediction in keyboard applications. Fed-GO-UCB operates under the coordination of a central server and multiple clients, ensuring data decentralization. The algorithm comprises two phases: uniform exploration and optimistic exploration, allowing clients to collaboratively minimize cumulative regret and make quality decisions during the learning process. The paper highlights the challenges in federated bandit optimization, particularly in constructing confidence sets for generic nonlinear functions and managing communication costs. Fed-GO-UCB addresses these issues through a novel confidence set construction and an efficient communication strategy. Empirical evaluations demonstrate the algorithm's superiority over existing federated bandit algorithms, particularly in approximating nonlinear functions. The paper also proves that Fed-GO-UCB achieves sub-linear rates for both cumulative regret and communication cost, making it a promising tool for decentralized machine learning applications involving sensitive data.", "questions": "1. How does the performance of Fed-GO-UCB compare with centralized global optimization methods, particularly in scenarios with a high number of clients?\n\n2. Can Fed-GO-UCB be extended to handle heterogeneous clients with different reward functions, and if so, what modifications would be necessary?\n\n3. What are the practical implications of the “mild conditions” under which Fed-GO-UCB operates, and how do these conditions influence the algorithm's applicability in real-world scenarios?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. Novelty: Fed-GO-UCB is a new approach in federated bandit optimization for generic non-linear function optimization.\n\n2. Theoretical Guarantees: The paper provides rigorous proofs for the sub-linear rates of cumulative regret and communication cost, ensuring the algorithm's reliability and efficiency.\n\n3. Empirical Validation: The effectiveness of Fed-GO-UCB is demonstrated through extensive empirical evaluations, showcasing its superiority in approximating nonlinear functions and its practical applicability.", "weaknesses": "1. Limited Discussion on Assumptions: The paper mentions “some mild conditions” under which the algorithm performs well, but it could provide a more detailed discussion on these conditions and their practical implications.\n\n2. Comparison with State-of-the-Art: While the paper demonstrates the superiority of Fed-GO-UCB over existing federated bandit algorithms, a more comprehensive comparison with state-of-the-art methods in decentralized machine learning would strengthen the paper's contributions.\n\n3. Over-reliance on Communication: The need for occasional communications to aggregate local learning parameters may lead to potential inefficiencies or delays.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)