Federated High-Dimensional Online Decision Making
Authors: Chi-Hua Wang
Wenjie Li
Guang Lin
Venue: Accepted by TMLR ()

Abstract: We resolve the main challenge of federated bandit policy design via exploration-exploitation
trade-off delineation under data decentralization with a local privacy protection argument.
Such a challenge is practical in domain-specific applications and admits another layer of
complexity in applications of medical decision-making and web marketing, where high-
dimensional decision contexts are sensitive but important to inform decision-making. Exist-
ing (low dimensional) federated bandits suffer super-linear theoretical regret upper bound
in high-dimensional scenarios and are at risk of client information leakage due to their in-
ability to separate exploration from exploitation. This paper proposes a class of bandit
policy design, termed Fedego Lasso, to complete the task of federated high-dimensional
online decision-making with sub-linear theoretical regret and local client privacy argument.
Fedego Lasso relies on a novel multi-client teamwork-selfish bandit policy design to per-
form decentralized collaborative exploration and federated egocentric exploration with log-
arithmic communication costs. Experiments demonstrate the effectiveness of the proposed
algorithms on both synthetic and real-world datasets.

Published in Transactions on Machine Learning Research (07/2023)
Federated High-Dimensiona Online Decision Making
Chi-Hua Wang
thiluawangggukke edu
Department of Statistics, University of California, Los Angles
Wenjie Li
k35498purdue.. edu
Department of Statistics, Purdue University
Guang Lin
guanglin Spardue..cc.mmm edu
Department of Mathematics, Statistics, Purdue University School of Mechanical Engineering, Purdue University
Reviewed OpenReview: https: //
https://openreview openreview. net/ fer/formm id= TjoM063fc9
Abstract
We resolve the main challenge of federated bandit policy design via exploration-cxploitttio Irade-off delineation under data decentralization with a local privacy protection argument. Such challenge is practical in domain-specific applications and admits another layer of complexity in applications of medical decision-making and web marketing, where high- dimensional decision contexts are sensitive but important to inform decision-makir making. Exist- ing (low dimensional) federated bandits suffer super-linear theoretical regret upper bound in high-dimensional scenarios and are at risk client information leakage due to their in- ability to separate exploration from exploitation. This paper proposes a class of bandit policy design, termed Fedego Lasso, complete the task of federated high-dimensional online decision-making with sub-lincar thcoretical regret and local client privacy argument. Fedego Lasso relies on novel multi-client teamwork-sellish bandit policy design to per- form decentralized collaborative exploration and federated egocentric exploration with log- arithmic communication costs. Experiments demonstrate the effectiveness of the proposed algorithms on both synthetic and real-world datasets.
1 Introduction
Federated bandits (Huang et al., 2021 Dubey & Pentland 2020) an emerging setting of decentralized sequential decision making that emphasizes on collaborate bandit learning and data decentralized decision making. Designing effective decentralized sequential decision making strategies requires resolving the fun- damental ixploratton-eexloittaa clients do not submit their raw data in any circumstance and one client should not have any chance to infer decision rule of another client based on shared information. In principle, clients in collaborate bandit learn- ing stage should be coordinated to explore available actions and gain information to inform future decision making. decentralized decision making stage, one client's decision should not depend on other client's 's information avoid risk of indirect information leakage. Thus, coordinate exploration and privacy protected exploitation are central challenges in federated version of exploration-exxloitatii exploitation trade-off. However, such trade-off admits another layer of complexity in the presence of high dintesiinnni decision context, especially in applications of medical decision making web marketing (Bastani & Bayati 2020). Consequently, fed- erated high-dimensional decision making problems lead challenges on both learning and decision making, On learning, the agent should adopt estimation method to handle high-dimensional context with designing smart sampling scheme; on decision making, the agent should only utilize local clients information to give final decision meet the purpose of federation. As a result, designing bandit sampling scheme smartly is the key to minimize the regret while protect local client privacy with data decentralization.
trade-off under data decentralization with local privacy protection, that is,

---

Published in Transactions on Machine Learning Research (07/2023)
Regret guarantee comparison for federated bandit with linear feedback functions. M number of clients; K : number of arms; T time horizon; dimension of the docision context.
Table 1:
Bandit algorithms
Regret (High-d d d= OTT)
Communication cost
Centralized Diiakooouloou et al. (2017))
O KM log (K)))
O(M&
Decentralized [Amani & Thrampoulidis (2020))
O / log (MT))
OddM²
Fed-PE Huang et al. (2021)
/ log( (KMT)) ((og) O(T7/4M)
O (Md2
Async-LinUCB [Li & Wang
(0211)
OddM log
Byzantine-Roobst (Jadbabaic et al. (2022)
O(T
Lasso Bandit (Bastani & Bayati (2020))
O(log M + log logT)""sh))
No communi cation
Teamwork Lasso (Wang & Cheng (2020)
( T)2 K sh)
OKKMdlog, (I O(K (T/Mdlog((//KQ))) (T/Kq))
Fedego Lasso work)
O M) (log T)² k
Existing works on federated bandits Huang et al. 2021 Li & Wang 2021 Jadbabaie et al. 2022 un- fortunately, only protect the local privacy of data. but not the local privacy of 'information'. That is, one client's dccision making, in current arts of foderatod bandits, are using other client's information. While their method protect local data privacy, they share the resulting information freely to inform collaborate decision making at the risk of indirect information leakage. More frequent the clients communicate with the central server, more risk on indirect information leakage. Such risk of information leakage is from the Upper Confidence Bound (UCB) approach (Auer) 2002 Li et al. 2010) utilized in current federated bandits works. The reason is that the UCB approach cannot. handle exploration and exploitation separately. In addition, Table D shows that existing federated (low-dined) )ow-dimenssonal) bandit works suffer super-linear regret in the region of high- high-dimensional scenario, where the decision horizon T scales with the decision context dimension d, i.c.
T O() Bastani & Bayali 2020
To avoid super-linear regret in the high-dimensional scenario require rethinking on exploration and exploita- tion. Our strategy is to design the decision making policy with (i) decentralized collaborative exploration and (ii) federated egocent ric exploitation. In (i), we coordinate all clients to commit same decision no matter their current decision context to study that decision's efficacy. Such coordination prevents leakage of deci- sion information and results in decentralized collaborative exploration. In (ii), we allow clients to commit decision to minimize the regret. Such selfish decision protect client decision information and results in federated egocentric exploitation.
their own
Major Contributions. We deliver novel architecture for federated high-dimensional online decision making and associated algorithms. Following that, we highlight our major contributions. (i) Fedego Lasso Algorithm. Federated-egocentrii Lasso algorithm (Fedego Lasso) exploits Lasso regression to learn sparse local reward models and to inform future decision without compromising local data privacy. In particular, it enables each client to compule personalized, low-dimensional local reward model, which we refer to as the client private Lasso, that utilizes client's unique decisions, actions and observations of local data. (ii) Convergence Rate and Regret bound. We establish convergence results of three type of Lasso estimates implemented in the proposed Fedego Lasso algorithms (Lemma 3.1 3.4 and 3.6. Such convergence guar- antees is not trivial given the non-i.i.d. properties of dataset collected during online decision making process (Remark L.2p. With these convergence rate results, we establish a theoretical regret upper bound (Theorem 3.7 for the algorithm performance of Fedego Lasso. (iii) Empirical Results Through a combination of synthetic and real datasets (PharmGKB, Medical MNIST) we show the benefits of Fedego Lasso (a) benefits of fedcration architecture and (b) benefits of recruiting more clients on further regret roduction and faster error rate convergence in real-world tasks including personalize dosage searching and medical image labeling.
Benefits of Fedego Lasso. We list benefits of Fedego Lasso over standard lincar contextual bandit learning (that learns a single reward model with no central server to share and no high dimensional decision context). (1) More efficient, effective and secure decision making procedure. By sharing the online-learned Lasso regression, each client can make more efficient and effective local updates at each communication round. Such update is beneficial in committing its own individual decision making. Besides, our federation architecture reduce the risks of indirect data leakage or inverse decision rule recovery. This is unlike standard
2

---

Published in Transactions on Machine Learning Research (07/2023)
linear contextual bandit learning where in heterogeneous setting requires several rounds of model updates to recover oracle policy, and thus hurls performance. (IT) Provable federaatio archilecture for online decision making with high-dimensional decision contert. Existing works on linear contextual bandit-based online decision making with high-dimensional decision context focus on the effect of sparsity-imspired methods on explore-exploit trade-off. Current state of related literature does not have work designing federation architecture to further facilitate explore-cxploit trade-off in bandit learning. To our knowledge, this is the first provable federation architecture for online decision making with high-dimensional decision context that demonstrates the benefit of cooperation.
3 Key Enhancements in Practical Applicability of Fedego Lasso over Teamwork Lasso and Lasso Bandit. Compared to Teamwork Lasso in Wang & Cheng (2020) and Lasso Bandit in [astani & Bayati 22000), our Fedego Lasso bridges the gap between data privacy restrictions and the need for effective decision making in joint data utilization scenarios. The first is to allow data sharing in multi-institutional contexts. While Teamwork Lasso assumes 'complete data sharing" scenario, which not the case reality, Fedego Lasso enhances data sharing by allowing clients keeping their data in house and only share the regression coefficients to do joint decision making. The second is to address privacy concerns from federation. The policy in Lasso Bandit and Fedego Lasso are infeasible in healthcare field due to the restriction from HIPAA regulations, which prevents client to share their data directly to the third party(e.g. central server). Our Fedego Lasso are HIPAA-compliant, since we only share the regression coefficient. but not the original data to the third party. The last enhancement is to enable privacy compliant joint decision making. Both Lasso Bandit and Fedego Lasso neglects privacy regulation on data usage, leading risk of violating HIPPA law. We design the policy of Fedego Lasso to align the modern data sharing standard, making our algorithms with broader applicability in reality.
Technical advancements on Lasso Bandit and Teamwork Lasso. Here we discuss our technical advancements on extending the theoretical analysis in Lesso Bandit and Teamwork Lasso to secure loga- rithm expected regrct in federated learning case. The first technical contribution is a finer control on the convergence rate of the federated Lasso 3d ( (equation 5 c.f. Lemma 3.4 This relies on redefining the "good event" in the federated learning case to ensure the probability bound on the "bad event" is independent of the number of client M. Such independence builds on right lower bound (c.f. equation 3) on the phase length q such that the aggregated estimate 3 to have non-asy con-asymptotic convergence rate of order O(1/M). Another key technical contribution is a finer control the convergence rate of the egoistic Lasso 3 (cquation 6 such that the contributions to regret is of order Oloog T). This relies on finding a right regularization level for the Lasso procedure to make sure the non-asymptotic convergence rate of 3 is of O(1/M) order, c.f. Lemma 3.6 In conclusion, we refine the proof on the non-asymptotic convergence rate on the Lasso procedure in Lasso Bandit and Teamwork Lasso such that the final regret of Fedego Lasso secure logarithmatic regret.
1.1 Related works
Federated bandits. Recent works have called attention to the topic of federated bandits. Shi et al. (202)) examine efficient client-server communication and coordination methods for federated MAB with personalization, using heterogeneous reward distributions at local clients. Zhu et al. (2021); Li et all (2020): Dubey & Pentland (2020) discuss how to protect local data privacy in federated bandits via differential privacy. Unfortunately, existing methods to solve federated linear contextual bandit suffer super-linear regret in high-dimensional scenario (d = O(T)), since their cumulative regret scales linearly in context dimension d (Table D. Our work advances these prior efforts by relaxing low dimension reward model assumptions to the case with high-dimensional decision context.
Lasso bandits. Bastani & Bayati 2020 first introduced linear contextual bandit with high-dimensional covariate and proposed the Lasso bandit algorithm. Follow-up works such as Wang et al. (2018) and Wang & Cheng (2020) improved the regret bounds and extended it to different problems. In contrast, another line of literature (Kim & Paik] 2019:; Hao el al., 2020: Oh et al., 2021 Li et al., 2022) proposed different style of algorithms for solving high dimensional bandit problems. However, these efforts consider a completely different bandit problems where K contexts are observed at each round and only one underlying parameter B is present for all arms. One way to possibly transfer results in Bastani & Bayatil (2020) and its follow ups into the other line of research, and compare them, is to concatenate all the parameter B he's for different
3

---

Published in Transactions on Machine Learning Research (07/2023)
arms into one long vector 3 (see notations in Section 1.2 and assume that the K contexts generated in each round are always "one-hot" with the same feature for all the arms. Our works advances the setting in (Bsstani & Bayati (2020) by designing federation architecture to ensure local data privacy security while delincating explore-cxploit tradeoff in online decision making with high-dimenstional decision context.
Comparison with Teamwork Lasso Bandit in Wang & Cheng (2020). Our bandit sampling policy design (Figure I and client-center communication scheme (Figure 2 advances the 'alternating two stage"
design in Wang & Cheng (2020) in the regard of client privacy protection. Previous work Wang & Cheng (2020) batch decision making also solves the federated decision making problem in this paper, by setting their Teamwork Lasso Bandit with a batch of clients. However, such approach requires all clients share their raw data to server to train a central Lasso to inform decision, while our Fedego Lasso allows clients keep their data, only share their individual Lasso estimates, and use aggregated Lasso to inform decision. Such fundamental difference of our Fedego Lasso advances Teamwork Lasso Bandit in Waan & Cheng (2020) into a more private exploration and exploitation design. For exploration stage (Blue; Figure while Wang Cheng (2020) access all clients' raw data for a leamwork Lasso estimate, our Fedego Lasso do not touch client's 's raw data but only their individual Lasso estimate for federated Lasso estimate (Federation step at Figure 2). For exploitation stage (Red; Figure D while Wang & Cheng (2020) access all clients' raw data for a selfish Lasso estimate, our Fedego Lasso allows clients to do egocentric
decision by keeping their local estimate private and do not share to center or other clients. While Wang & Cheng (2020) raise algorithmic privacy concerns in the scope of federated decision making, our work makes contributions to federated nigh-dimensional decision making problems.
1.2 Notations and basic problem formulation
Here we give problem formulation and define the bandit algorithms regret and the Lasso estimator.
Federated high-dimensional online decision making problems. We investigate a federated linear contextual bandits scenario in which M clients are pulling the same set of K arms, represented by [K] := 1. K. Each client m E [M] at each time t E [T] pulls an arm E [K] based on historical information. The expected reward of pulling arm k at decision context x the inner product (x, B&) between x and the reward parameter 3x. Additionally, there a sparsity parameter so E [d], defined the smallest integer such that for all & E [K], ||Bxllo S so.
Regret of bandit algorithms т. A bandit algorithm of client m pulls arm (m) at decision step t. The objective is to design bandit algorithms x that minimizes the expected cumulative regret among all clients, defined as: (T)
EM ΣT (<z))) B.Am).
- ( -B,mm))] where k(m)), E [K] is a context-specific
(m) optimal arm such that vt + (m)). ((((")) BBamrr)) 2 (a(m), ()).
In this work, we approach the above federated high digeniimensional online decision making problems with LASSO regressions.
Definition 1.1. (Lasso regression estimator) Given a dataset D = ((XY)), where Y is a [D]-dimension response vector and X is a |D] x d decision context matrix from the dataset D. The Lasso regression estimator with regularization level X 2 0 is defined as
3 (D,A) = arg min {|Y X311//D/+A1I A1811)
(1)
Remark 1.2. (Non-i.i.d. propertics of datasct D.) Duc to the nature of online decision making, the Lasso estimate is trained on datasets D that cannot satisfy typical distributional (or i.i.d.) assumptions in the literature of federated learning. The key reason is that the decision at certain time steps are depend- ing on previous history, leading to dependency between decision and historical data. Therefore, standard convergence theory is not applicable for analyzing Lasso trained on the dataset D. Fortunately, it still possible to analyze and design the statistical properties of the trained Lasso estimate if we carefully design the bandit policy to coordinate the exploration across clients and exploitation within clients during whole online decision making process. See Figure D and Section 3.1 for bandit sampling design and Section 3.2 for formal convergence results of trained Lasso estimates.
Remark 1.3. (One the usefulness of Lasso regression estimate) We use Lasso since our application is in e-commerce and medical setting. In such setting, the context vector is often high-dimensional, but only
4

---

Published in Transactions on Machine Learning Research (07 (07/2023)
&
&
&
&
S.
Client
&
&
Clent M
Figure 1: Centralized teamwork-selfish sampling policy. In the teamwork stage (Blue), all clients pull prescribed arms, no matter the current decision context, to form collaborate exploration for a quick recovery of arm reward parameters. In the selfish stage (Red), all clients pull the arm with highest estimated reward for current decision context to form egocentric exploitation for maximizing their own cumulative reward, Each stage has length Kg, where K is number of arm and q is the teamwork unit length (See Section 3.1 for details.)
few number of variable are decisive. Lasso captures such property by assuming the sparse structure of the regression coefficients. With such sparsity structure of regression coefficient, we leverage the technique in high-dimensional statistic in our theory (Theorem 3.7). The Lasso bandit [astani & Bayati (2020) paper explains that in medical applications, we might want to identify a small number of biomarkers that are associated with a certain disease. In e-commerce applications, we might want to select a small number of features that are relevant for predicting user behavior. Both of these problems can be formulated as a sparse linear regression problem, where we want to minimize the number of non-zero coefficients in the regression model. Lasso is particularly useful in these cases because it performs both feature selection and regularization simultaneously. By penalizing the L1 norm of the regression coefficients, Lasso encourages sparsity and tends to produce models with a small number of non-zero coefficients. This can lead to better generalization ion performance and easier interpretability of the resulting model. Therefore, the motivation for using Lasso is to take advantage of its ability to perform feature selection and regularization simultaneously, which is particularly useful for applications where sparsity is assumed.
2 Federated online decision making
This section elaborates horizontal federated learning (as defined in Yang et al. (2019) )) version of bandit problems with high-dimensional decision context and linear arm rewards (as rndredee by Bastani & Bayali (2020) and others). The three main challenges arise from federated contextual bandits are (A) Model local datasct heterogeneity. (B) Tighten local data and decision rule privacy security. (C) Coordinate efficient central communication. Section 2.1 established our framework to resolve these challenges.
2.1 Resolution to federated high- digeeniinnii bandit challenges
A. Client local bandit models for local dataset heterogeneity. To account for the intrinsic correlation between rewards associated with different clients pulling the same arm, we assume the local bandit model of client m that the expected reward of pulling arm & is a linear function of the decision context TG formally,
r r(x)) (Bk, + (mm)
(2)
The parameter 3x Idd is constant but unknown vector for each arm k E [K]. The noise procoss {(c (m)) : ((m)) )ET() is assumed to be a a susuGaansian martingale difference sequence (that is, Fl(e(()) (mm) F(m) 0 andElexp(>ee" (m))))))))))))))) F(()) S exp(o2X2/2) for all real A). See Section 2.2 for essential statistical regularity assumptions for analyzing foderated contextual bandit algorithms. The local dataset heterogeneity is depicted naturally by the local bandit model equation 2 since clients have their own decision context sequence {- (0)) JT resulting heterogeneous reward distributions.
B. Federation with decision rule hiding to tighten local privacy security. Our proposal to resolve local data privacy dilemma is via Teelish sampling policy (Figure [ By local data privacy, we
5

---

Published in Transactions on Machine Learning Research (07/2023)
meant that one client should not have any chance to infer decision rule of another client based on shared information. To protect local data privacy, we design lederation architecture and hide clients' decision rules from central server. Our approach, in the spirit of the doubling trick (Besson & Kaufmann 2018): : do not require the agents to share to the server their datascts, no matter the datasetes are collected from Teamwork mode or Selfish mode. The only information to share is the Lasso estimates trained on datasets collected during Teamwork mode at certain pre-specífied decision points. Thus, the Teamwork-Selfish bandit policy resolves the local data privacy security challenge.
C. Horizontal federation to coordinate efficient communication. In horizontal federated-Learnineg system, M clients with same online decision making task collaboratively Iearn model with the help of server. We resolve explore-exploit dilemma via client-center communication protocol (Figure 2), established at Section 3.3 In our scheme, each client trains two Lasso estimates, one from Teamwork dataset (for exploration) and the other from Teanwork-Selfihh aggregation dataset (for exploitation). Our strategy is to introduce two different modes for agent: Teamwork mode and Sclfish mode. Clients only upload their Lasso istims at. the end of the Teamwork mode, thus the communication cost is log(T/Kg) Kg). Our approach, which in spirit is applications of horizontal federated learning architecture (Yang et al. 2019), coordinates efficient communication between clients and center to perform near-optimal decision making and achieve logarithmic regret performance. Consequently, the communication protocol (Figure 2 resolves the local
data privacy security challenge.
2.2
Statistical Regularity Conditions
list essential statistical regularity assumptions towards convergence rate analysis of Lasso regression estimator (Definition L.1 and regret analysis of algorithms. We note that these assumptions are standard in the literature of high-dimessional decision making (Bastani & Bayati 2020
In section 2.2
Assumption 2.1. For all clients m E [M], there exists Co 2 0 such that for arms kn # h2 in A, the distribution of decision context X satisfy P(I(X, g(()) د(m))| (0) I Cak for given K >> 0.
Assumption 2.1 is known as Margin Condition in the classification literature [Tyybkov al. (2004) Such
condition ensures only minor fraction of docision context is sampled near the classification boundary
{a: (x. Skg )ba)== 0} in which efficacy of both arms are indissinguseeable [Rusmevichienlong & Tsitsiklis,
2010 Wang & Cheng, 2020).
Assumption 2.2. For all clients m E [M], there exists a optimality gap constant h and two mutually exclusive arm subsets hopt and Avub with [K] = Aopt U A such that (a) For each arm is in Agab: it holds for every decision context x E X that (Bx, x) < max (Ba, æ) - and (b) For each arm exists a constant p. > of minimal sampling probability such that minkekope P(X E Un) 2 Mp, where X ()) > max (Ba, h).
hopt: there
UR (I E
Assumption 2.2 is known as the Arm Optimality Condition (Bastani & Bayati 2020 Wang & Cheng 2020 Such condition separates arms into optimal subset Aopt and suboptimal subset Asub, in the sense that (a) all sub-optimal arms are strictly sub-optimal for every decision context and (b) each optimal arm k E Aopt is strictly imal for some decision context. ( UR at Assumption 2.2).
Assumption 2.3. For a client m, there exists a constant de > 0 such that for each optimal arm h E Aopt: its population covariance matrix Σg = E[XXT [X e Uk] belongs to the compatibility set with respect to the true parameter Bt. That is, Σg E C(supp(5))) (o), where
0( = { {A RPXP Ve E Hº | s (1 Au) (4)()AA if || $3 31122/h1
Assumption 2.3 referred to as the Compatibilily Condition in high-dimensionall statistics Bühlmann & Van De Geer 2011). It ensures that the Lasso regression estimator trained on samples X E Us converges to the true parameter 3e with high probability as the number of samples grows to infinity.
3 Fedego Lasso algorithms
Algorithm | presents our solutions, the Fedego Lasso bandit algorithms, to the federated online dccision making problems established Section [ There are 3 key components our design of Fedego Lasso algo- rithms: the teamwork-sellish bandit sampling strategy (Figure 1) the clients-central server communication
6

---

Published in Transactions on Machine Learning Research (07/2023)
protocol (Figure 2 and local data privacy preserving. Section 3.1 establishes the teamwork--elfish bandit
sampling strategy to implement sparsity-award collaborate exploration. Section 3.2 illustrates how Fedego
Lasso protect local clients privacy. Section 3.3 establishes the communication protocol of resulting Lasso estimates between clients and central server towards optimal regret performance online decision making task.
Algorithm 1 Fedego Lasso: client
Require:
Decision horizon T, number of arms K, optimality gap h(m), Teamwork stage T.
for t = I...T do
Observe the decision context (mm
if t E T(Teamwork mode) then
T(z( (m)) (o (m))
.) (Alg 2
end if
if t & T (Selfish mode) then
K- FedScreen(r) (m)
(mm),
k.t (. h!m)) (Alg where A is the central federated Lasso estimate
1
defined equation 5)
-()("))= = EgoCommi t( (22, )
(mm)
(Alg where (m)) is the private egoistic Lasso estimate
defined at equation 6)
end if
Pull the arm ((x(")), receive reward rt (m)
end for
Return: Cunulative reward R(T)- Σt= (m)
3.1 Sernwork--Sllfstee bandit sampling
This section presents the three key elements implementing the teamwork-selfish bandit sampling strategy (Figure []: sampling mode, resulting datasets and their Lasso estimates.
Teamwork and Selfish. Every local client agent has two sampling modes: Teamwork mode (Blue block in Figure ! and Selfish mode (Red block in Figure D. In the Teamwork mode, all clients runs collaborate exploration, aiming at a quick recover of the arm reward parameter set { In Selfish mode, clients run egocentric exploitation individually, aiming at an optimal decision for their own current decision context. The design of alternating sampling guarantecs the convergence Lasso while optimizing algorithm performance.
Sampling modes:
Datasets:
teamwork set T and selfish set S. Every local client agent maintains two datasets: teamwork dataset T and selfish dataset S. In general, datasets ((m) and g(m) collect samples from Teamwork and Selfish mode respective for the client m. In particular, notations 7.(m) and s(m)
[c], denote the teamwork and selfish dataset respectively from pulling arm & during decision period [4] = 21, ... ,I.. Such maintenance is to separate the data source. Technically, the teamwork set's 's decision is public due to agreement of all clients. The selfish set's docision is private and only accessible by the client itself. Theorctically, the tcamwork set's samples are independently distributed since in which the decisions are independent. of the previous history, while in selfish set the samples are dependent since the decisions are dependent the history.
10,,k
Estimates: teamwork Lasso 3: and private Lasso 36 Every local client agent maintains two Lasso est intimates: client teamwork Lasso and local private Lasso. Tn principle, the client leamwork Lasso 3 = (T)) is from running Lasso regression (Definition 1.1 on the Teamwork dataset; in contrast, local private Lasso 3 3T US is trained on the aggregation dataset of Teamwork and Selfish set. Such maintenance is to to separate federation and decision making. In Fedego Lasso algorithm, all local clients upload their client teamwork Lasso to central server at the end each Teamwork mode to facilitate federation. At each decision step in Selfish mode, all clients commit final decisions based on local private Lasso estimate.
7

---

Published in Transactions on Machine Learning Research (07 (07/2023)
3.2 Decision rules in Teamwork and Selfish mode
This section presents the three key subroutines implemented in the Fedego Lasso bandit algorithms (Algo- rithm 1 collaborate exploration (Algorithm 2). foderated screening (Algorithm 3) and egocentric commit-
ment (Algorithm 4
A. ColExplore: Collaborate exploration
Here we introduce 3 key quantities in the Collaborate exploration stage Algorithm | The phase length q determines the block size of each stage Figure ] reflecting the communication frequeney. The Teamwork stage T the teamwork stage (blue block) in Figure I in which the decision in this stage only depends on the timestamp but not depends previous response history. Last, the sample collected at the tcamwork stage is used to learn the Lasso regression coefficient for each client and to be shared to the central server.
Algorithm Co1Explore(z,tt
Input: decision context z, decision step t Output: <(x) = mod K)
Phasee length q. key technical challenge to determine the phase length q to ensure Lasso estimalor convergence is fast enough informal optimal decision making.
20 4C2(01)² q 2 Steamwork = max Mp. Mp.
512m max log d (4 + log M) M2pp))
(3)
(2) Planming of Teamwork stage T. Each block in Figure D contains Kq decision steps. The planning of teamwork stage is T =, (T/Kg) Tn, where the nth Teamwork stage is
T, = [(2" 1)Kq + 1: :22"
(3) Client teamwork Lasso. Lasso regression (Definition 1.1
The client teamwork Lasso for client m at time step is defined by running in the teamwork dataset (m), T(m)) formally,
BL B A1).
(4)
Lemma 3.1 justifics the convergence of client tcamwork Lasso equation
Lemma 3.1. (Deviation incquality of client teamwork Lasso) For all arms [K], the client teamwork Lasso estimate equalion salisfies
IP (1138.6m)) - BBull > h/ h/44max)
S 5/Mtt
if x(m) Mp. and q Qteamwork-
Proof. See Section Lemma 3.1 generalizes the forced sampled Lasso in Bastani & Bayati (2020) into horizontal federated learning scheme. The key difference is to redefine the length of exploration Itesmwork to ensure faster concentration. Finding Iteamwork is non-trivial due to the centralized exploration scheme. Our found solution is to inflate the length of exploration by log M factor, that is, feeawwor O(go log M), where is the exploration length in Bastani & Bayati (2020).
Remark 3.2. (On the concern of the situation that proportion of clients explore the same arms) In current design of Collaborate exploration scheme, subset of customers may keep exploring the same arms. Such possibility raise concerns fairness of the decision making procedure. In particular, it is challenging to ensure fairness in the allocation of experimental resources. These customers may miss the opportunity to try their best arm, bearing the experimental costs for joint research. To address this issue, a significant challenge we anticipate is to 'define a regret formulation that sufficiently reflects decision fairness. Are there minority groups among the clients? How can we ensure that the results of joint dccision-making benefit everyone instead of some clients bearing the costs while others enjoy the outcomes? These are non- con-trivial questions and challenges we expect to encounter.
8

---

Published in Transactions on Machine Learning Research (07 2023)
B. FedScreen: Federated screening.
At each time step in Selfish mode, the client screen available arms with central federated Lasso. In this stage, the goal of Algorithm 3 is to screen out sub-optimal arms for a given decision context. The screening is based on the central federated Lasso regression estimate equation whose statistical accuracy is supported by Lemma 3.4 After the screening, we are sure that the remaining candidate arms are located in the Aopt.
in Assumption 2.2 and contribute most h in the formal regret.
Algorithm 3 FedScreen(z,
Input: decision context x, federated estimates { (central lederated Lasso estimate equation 5 optimality gap
Output: the candidate set k(x) { E A (z, Be) 2 max Bi) h/2]
Central federated Lasso. After receiving all clients' teamwork Lasso estimates, the central server performs federation by computing the central federated Lasso. The central federated Lasso for arm at decision step is defined as the average of all client. Teamwork Lasso estimates; formally
M Σ m=1
= M
a5.(m) ktt
(5)
Remark 3.3. Note that the central federated Lasso is the average of teamwork Lasso estimates, which are trained on i.i.d. samples, and therefore has convergence guarantees. Such analytical advantage due to our policy design that all agents explore the efficacy of pre-specified arms during Teamwork mode (Blue block in Figure 1
Lemma 3.4. For all arms & E [K], 1 (Kq)², the central federated Lasso estimate equation satisfies
P (1 3xll1 (m)) /4.max/ s 5/1².
Proof. See Section B The key is due to tighter control of client teamwork Lasso (Lemma 3.1 control ensure the deviation probability of equation 5 is independent of client number M. Remark 3.5. One can directly apply force estimator deviation inequality in Bastani & Bayati 2020 but the resulting deviation probability will depends on client number M due to union bound. Our technical contribution is to remove such dependency on M by inflating the exploration length by log M factor.
Such
C. EgoCommit: Egocentric commitment
Given the resulted set of optimal arm candidates ((((()) for decision context (m) from the federated screening (Algorithm g the client agent commits to the arm with the highest estimated expected reward estimated by the private egocentric Lasso equation D
Algorithm (g)))mmit(A((x). (3
Input: candidate set [x),, decision context x, private estimates ( (private egoistic Lasso estimate equation 6
Output: ((x = arg sa (t, (x,
The private egoistic Lasso for client m at time step & is defined by running Lasso regression (Definition 1.1 in the teamwork-selfish aggregate dataset (m) U ((m). formally,
Private egoislic Lasso.
3b.(m) Pk.t
= (T U U (mm)
(6)
Lemma 3.6 juis the convergence of private egoistic Lasso equation

---

Published in Transactions on Machine Learning Research (07 (0722)23)
Upload
Federation
Broadcast
IIII
Center
Center
Lewe
Leaso I Paytel
M
1
M
Client
Client m
Glent
Client
Client m
Client M
Federated client-center communication. At the end of each Teamwork stage (Blue block in Figure all clients uploads their current teamwork Lasso estimate (defined at equation 4 to the central server. Then, the central server perform federation to compute the federated Lasso estimates (defined at equation 5 Last, the central server broadcast the federated Lasso estimates to all clients for their upcoming federated screening procedure in the Selfish stage (Red block in Figure
Figure 2:
Lemma 3.6. For all optimal arms k E Aopt set 2,t egocentric Lasso estimate equation satisfies
(m) d0
M dog and & 2 Cs. Then, the private V
3250
Cileolp.t
P( Balli 16 / (otd (0o) Mt))
S 2(((M)) +xp((p2((3M233333
Proof. See Section
C The key is to refine the estimation error of Lasso estimator.
3.3 Events-Central Server Communication
Figure Figureppresee prosents the three key events in the clients-contral server communication protocol: upload, federation and broadcast. In the following we discuss the contribution of such horizontal federated learning architecture to bandit learning and local data privacy security.
Upload: Clients upload local tcamwork Lasso to server. At the end of cach round of the Teamwork mode, all clients upload their current client Teamwork Lasso estimates equation 4 to the central server facilitate the federation. The local teamwork Lasso have difference convergence level due local data heterogeneity. The collaborate exploration between clients in Teamwork mode ensuring decisions of client will not compromise to the other client. Such advantage is due to design of Teamwork-Sefie sampling strategy, all clients do experiment for collaborate exploration during Teamwork mode.
Federation: Server compute central federated Lasso. The central sever do averaging to mitigate statistical error received teamwork Lasso estimates. The outcome estimate is called central federated Lasso (defined at equation 5 The federation event helps security by ensuring internal potential privacy Ieakage from the central server since clients do not upload any datasct but only their local tcamwork Lasso estimates.
Broadcast: Server broadcast federated Lasso to clients. After federation, the central server broad- casts to clients the central foderated Lasso equation 5 helping client to do valid screening procedure to exclude sub-optimal arms and find out the candidates of optimal arms. Such screening procedure is termed federated screening and elaborated at Algorithm The broadcast event helps security by the fact that one client cannot infer other clients' decisions basod on the foderated Lasso, since the final decision based on private egocentric Lasso (Eq. 6 as in Algorithm A Such feature helps us avoid internal potential privacy leakage from one client to the other.
10

---

Published in Transactions on Machine Learning Research (07 2022)
350 USG50
Sarek Fedage LAG0 lands
Bard: Fadgee JdSO Gard1
ledage LKGOO Sundit
0.5
0.00
1133
044-
1233
100
020
2003 Dettiit Nort
Destoics Nott
Cecoran
(a)
Synthetic Data
(b) PharmGKB
(c) Medical MNIST
Figure 3: Comparison of the performances of Lasso bandit in Bastani & Bayati 2020)) Teamwork Lasso bandit, and Fedego Lasso bandit algorithms. Fig (a). Average cumulative regrets per client synthetic data. Fig (b). Error rates on the PharmGKB dataset. Fig(c). Average cumulative regrets per client on the Medical MNIST dataset.
Ued
752
2.2
3,40
3325
5000
Dcstice
Tuint
(a) Synthetic Data
(b) PharmGKB
(c) Medical MNIST
Figure 4:
The performances when the number of clients increase. Fig (a). Average cumulative regrets per
client on synthetic data. Fig (b). Error rates on the PharmGKB dataset. Fig(c). Average cumulative regrets per client the Medical MNIST dataset.
3.4
Communication cost and Regret guarantee of Fedego Lasso
The following theorem bounds the regret of Fedego Lasso bandit algorithm (Algorithm 1
Theorem 3.7. The communication cost of Fedego Lasso is (Tlog,(T/Kq)) The regret of Fedego Lasso bandit algorithms æ over decision horizon [T] satisfies
Regret, (T) = Olog M logg T + logd
Proof. See Scction D for details. The result supports that Fedego Lasso is the first federated bandit algorithms (compared to others in Table M that secures sub-linear regrel in high-dimensional scenario. Additionally, if we transfer the problem into the setting of Kim Paik (2019); Hao et al. (2020); Li et al. (2022) as mentioned in Scction [.1 both regret bounds their works and our work are logarithmic in the dimension d. However, their regret bounds are either of order O(VT) or O(T2/3), while our regret bound is logarithmic in T and the dimension d. The advantage comes from not only unique algorithm design, but also the difference in problem setting and the assumptions in Section 2.2
4 Empirical results
While the theoretical regret analysis (Theorem 3.7 provides worst-case guarantees for Fedego Lasso, we now examine their performance on a variety of tasks empirically. Examination conducted using both synthetic and real-world data.
A. Experiment setup. We compare Fedego Lasso bandit with the vanilla Lasso bandit algorithm in Bastani & Bayati 2020 and the Teamwork Lasso bandit algorithm Wang & Cheng (2020) the three
11

---

Published in Transactions on Machine Learning Research (07 (07/2023)
datasets. We run each algorithm for 10 independent trials on each dataset and plot the average results with two standard deviations. Additional experimental details are provided in Appendix F (a).Sytlhelic Dala. The sparse parameters { ===1 for each client generated from randomly sampled support, and then the nonzero parameter values are generated from the uniform distribution on [0.1]. The decision context are drawn randomly from multivariate normal distribution. (b).Real Real data: PharmGKB. The first real-world task is personalized dosage searching. The Pharrmacogeoomics Knowledge Base (PharmGKB) dalaset was used by Bastani & Bayati (2020) to support the superiority of Lasso bandit over the other bandit algorithms. We inherit their settings and investigate the error rates of the two algorithms when giving warfarin dosages based on patient-level decision context such as demographics, diagnosis, and modications. (c).Real data: Medical MNIST. The second real-world task is to collaborate classification of Medical MNIST images.. To extract the useful features vectors from the medical images, we first train a fully-connected neural network the dataset till it reaches good training and testing accuracies. At cach round of the bandit problem, image is sampled from the dataset and fed into the neural network. The covariates for the bandit algorithms are the output of an intermediate layer of the neural network. We define the instantaneous regret by whether the image is correctly classified.
B. Benefits of federation architecture. Figure supports the benefits of federation architecture enjoyed by the proposed Fedego Lasso over the other baselines. In synthetic data scenario, Fedego Lasso enjoys substantial regret reduction in Figure 3 (a). In the task of personalized dosage searching, Fedego Lasso enjoys faster error rate convergence in Figure (b). In the task of medical image labeling, Fedego Lasso again enjoys substantial regret reduction in Figure (c). These empirical evidences supports the benefits of the proposed federation architecture.
C. Benefits of large number of clients. Figure supports the benefit, of having large number of clients in federated bandit learning. In the synthetic data and the task of medical image labeling, Fedego Lasso enjoys further regret reduction by recruiting more clients in bandit learning, as supported by Figure | (a) and (c). In the task of personalized dosage searching, Fedego Lasso with more clients enjoy faster error rate convergence, in Figure 4 (b).
5 Conclusion
We build novel architecture federated linear contextual bandits model with high-dimensional decision context. Such architecture delivers unified federated bandit framework that resolves local dataset het- crogeneity, local data and decision rule privacy socurity and explore-cxploit tradcoff simultancously. The associated algorithm Fedego Lasso utilizes the sparse structure of local bandit models to recover the global parameters and inform efficient. federated exploration with effective egocentric exploitation. Theoretical analysis supports that Fedego Lasso secures sub-linear regret in the order of O(log M (log 2)) with com- munication cost in the order of (T)gg(T)Kg))
References
Yasin Abbasi- Yadkori, David Pal, and Csaba Szepesvari. Online-to-confidene--s conversions and applica- tion to sparse stochastic bandits. In Artificial Intelligence and Statistics, pp. 1 1-9, 2012.
Alckh Agarwal, John Langford, and Cu Wei. Foderated residual lcarning. arXiv:2003.1 12880, 2020.
arXiv preprint
Shipra Agrawal and Navin Goyal. Analysis of thompson sampling for the multi-armed bandit problem. In Conference on learning theory, pp. 39-1. JMLR Workshop and Conference Proceedings, 2012.
Shipra Agrawal and Navin Goyal. Further optimal regret bounds for thompson sampling. In Artificial intelligence and statistics, pp. 99-107. PMLR, 2013a.
Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoffs. In Inter- national Conference on Machine Learning, pp. 127-135. PMLR, 2013b.
Noga Alon and Joel H Spencer. The probabilistic method. John Wiley & Sons, 2004.
12

---

Published in Transactions on Machine Learning Research (07/2023)
Sanae Amani and Christos Thrampoulidis. Decentralized multi-agent linear bandits with safety constraints. arXiv preprint or 0tt:2012.00311 2020.
Yoshinori Aono, Takuya Hayashi, Lihua Wang, Shiho Moriai, et al. crivacy-preeerving deep learning via additively homomorphic encryption. TEEE Transactions on Information Forensics and Security, 13(5): 1333-1345, 2017.
Peter Auer. Using confidence bounds for exploitatiioneexlloratinn trade-offs. Journal of Machine Learning Research, 3(Nor):397-422 2002.
Peter Auer, Nicolo Cesa-Biande and Paul Fischer. Finite-tima analysis the multiarmed bandit problem. Machine learning, 47(2):235- 226--266, 2002.
Hamsa Bastani and Mohsen Bayati. Online decision making with high-dimensional covariates, Operations Research, 68(1):276-2)) 2020.
Lilian Besson and Emilie Kaufmann. What doubling tricks can and can't do for multi-armed bandits. arXiv preprinl 1rx: 06971, 2018.
Sébastien Bubeck and Nicolo Besa-Bianchi. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Machine Learning, 5(1):1-122, 2012.
Peter Bühlmann and Sara Van De Geer. Statistics for high-dimensional data: methods, theory and applica- tions. Springer Science Business Media, 2011.
Liam Collins, Hamed Hassani, Aryan Mokhtari, and Sanjay Shakkottai. Exploiting shared representations for personalized federated learning. arXiv preprint arXiv:100.007078, 2021.
Maria Dinakopoulou, Susan Athey, and Guido Imbens. Estimation considerations in contextual bandits. arXiv preprint arXic:1711.07077, 2017.
Abhimanyu Dubey and Alex Pentland. Differentiall--riiate federated linear bandits. arXiv preprint arXiv:2010111425 2020.
Alexander Goldenshluger and Assaf Zeevi. A linear response bandit problem. Stochastic Systems, 3(1): 230-261, 2013.
Botao Hao, Tor Lattimore, and Mengdi Wang. dimensiimaii sparse linear bandits. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Sys- tems, volume 33, pp. 10753 10763. Curran Associates, Inc., 2020. URL httpp::/pproceednggs. neurips. Paper. pdf
Ruiquan Huang, Weiqiang Wu, Jing Yang, and Cong Shon. Federated lincar contextual bandits. In Thirty- Fifth Conference on Neural Informalion Processing Systems, 2021.
Ali Jadbabaie, Haochuan Li, Jian Qian, and Yi Tian. Byzantine-robust federated linear bandits. preprint XrXi::2204.01 01155,, 2022.
arXiv
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurólien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Advances and open problems in federated learning. arXiv preprint arXiv:1912.0400 2019.
Gi-Soo Kim and Myunghee Cho Paik. Doubly-robust lasso bandit. In H. Wallach, H. Larochelle, A. Beygelz- imer, F. d' d'Alché-Bue, F. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems. volume 32. Curran Associates, Inc., 2019.
Jakub Konečný, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Thoertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arXio preprint arXiv:1610.05.4 92, 2016.
13

---

Published in Transactions on Machine Learning Research (07/2023)
Tze Leung Lai and Herbert Robbins, Asymptotically efficient adaptive allocation rules. Advonces in applied mathemalics, 6(1):4-22 1985.
John Langford and Tong Zhang. Epoch-greedy algorithm for multi-armed bandits with side information. Aduances in Newral Information. Processing Systems (NTPS 2007), 20:1, 2007.
Chuanhao Li and Hongning Wang- Asynchronous upper confidence bound algorithms for federated linear
bandits. arxiv preprint urX1v:2110001463, 2021.
Lihong Li, Wei Chu, John Langford, and Robert E Schapire. A contextual-bandit approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web, pp. 661 670, 2010.
Tan Li, Linqi Song, and Christina Fragouli. Federated recommendation system via differential privacy. In 2020 IEEE Internalional Symposium on Informalion Theory (ISTT), pp. 1592-2599 IEEE, 2020.
Wenjie Li, Adarsh Barik, and Jean Honorio. simple unified framework for high dimensional bandit problems. In Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 12619-12655. PMLR, 17-23 Jul 2022.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication--ffcieedl learning of deep networks from decentralized data. In Artificial intelligence and statistics, pp. 1273-1282. PMLR, 2017.
Min-Hwan Oh, Garud Iyengar, and Assal Zeevi. Sparsity-agnostic lasso bandit. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 8271 8280. PMLR, 18 24 2021.
Vianney Perchet, Philippe Rigollet, et al. The multi-armed bandit problem with covariates. The Annals of Statistics, 41(2):693 721, 2013.
Paat Rusmevichientong and John N Tsitsiklis. Lincarly parameterized bandits. Mathematics of Operations Research, 35(2):395-411, 2010.
Chengshuai Shi, Cong Shen, and Jing Yang. Federated multi-armed bandits with personalization. In Inter- national Conference on Artificial Intelligence and Statistics, pp. 2917-2925 PMLR, 2021.
Alexander B Tsybakov et al. Optimal aggregation of classifiers in statistical learning. The Annals of Statistics, 32(())135-166) 2004.
Chi-Hua Wang and Guang Cheng. Online batch decision-making with high-dimensional covariates. In International Conference on Artificial Intelligence and Statistics, pp. 3848-3857 PMLR, 2020.
Xue Wang, Mingcheng Wei, and Tao Yao. Minimax concave penalized multi-armed bandit model with high-dimensional covariates. In International Conference on Machine Learning, pp. 5200 5208. PMLR, 2018.
Qiang Yang, Yang Liu, Tianjian Chen, and Yongxin Tong. Federated machine learning: Concept and applications. ACM Trunsactions on Intelligent Systems and Technology (TIST), 10(2): 19, 2019.
Zhaowei Zhu, Jingxuan Zhu, Ji Liu, and Yang Liu. Federated bandit: A gossiping approach. In Abstract Proceedings of the 2021 ACM SIGMETRICS/ ChiTTIIICS/ttteraaiinnall Conference on Measurement and Modeling of Computer Systems, pp. 3 4, 2021.
14

---

Published in Transactions on Machine Learning Research (07 (07/202) /022)
A Proof of Lemma 3.1
The proof strategy is to use Lemma E.1 the dataset (T())) ). We first prove three lemmas for bounding probability of bad events. Then combines these results to gain deviation inequality of Teamwork Lasso under FedEgo bandit sampling scheme.
The following lemma gives a high-probability lower bound of the optimal allocation rate in the dataset (1,.k)
Lemma A.I. If 2 (Kq)², the Sollowing holds
KT (m) [t
Mp 2
P
(7)
M
Proof. Recall version of the Chernoff incquality: given a sum of mutually independent indicator random variables with expectation Elyy], one has that Plly - μ4| > ///2| < 2exp(-n/10),
Probability upper bound on the expected optimal allocation number. Consider the indicator of optimal allocation variable I[(a E (T y) for all a (T())) Assumption 2.2 implies that the expected opti-
mal allocation number μ T [Ta E (T(())) is at least Mp. (Tpp((TT.
(n [t], ) that is, μ Mp.1(T(m)) "i.k I- Tn
this case, the Chernoff inequality indicate a high-probability upper bound on the optimal allocation number (TT))) as
Mp- (ma) Pll P (m))) [t],k
Mp.
[4]. ((TT)).)))
II < 2exp(
(TT),x) )l)
(8a)
2
10
Recall that 1(T))))) (1/2)q logt. The equation equation Sa becomes
Mp.
KT(T))
2 2xxp(-
Mp.
q log t).
(8b)
2
20
(4 + log M). The equation equation 20 Require q 2 Mp.
8b
becomes
PI((T(m)
(m)
Mp.
(m)) [t].A
Il 2 2exp(-(A1ogg log M)) M
2
(8c)
The following lemma gives the probability upper bound of the failure of compatability condition of sample covariance matrix dataset (T Lemma A.2.
Φ1 P (S(TTT))) e (upp(3))
V2 )
1
2
(9)
Mt
Proof. By an application Lemma EC.6 Bastani & Bayati 2020), we first have
P E((T(())
EC suppp()), d 2 1 (1-exp(-C2(0))((TT
)]
)
(10a)
Recall that ((T(m)) 2 (1/2)qlog) Lemma A.1 indicates that with probability at least = 2/Mt*,
(T [),k
(m)
y
Mp.
[1,,k
(ma)
)
2
Mp.
q
glogt
(10b)
2
4
15

---

Published in Transactions on Machine Learning Research (07/2023)
Require q 2 (Ca(d:)² Mp. (4 log M). The equation equation 10a becomes
IP (1)))) & c (Supp((), Φ1 (2)
)
s exp( expp(((40p)) log + log M)) Mt
(10c)
0
Lemma A.3. Set 2(m²)=
Then we have,
2 (2|= (gexx(()) /1(T//2)1) s a(m)) /2) 2 M
max rEld]
(11)
Proof. Recall that (TTT)) 2 (1/2)q logt. Require
2
512x lng 21(0)
(4 + log M). we have
exp
Cil
MMp
(m)
)2
log d
2
40mmax
h²
S exp
(i)
59logt
log dl
16
16x mmx
C² q glggt + log
=xx
512r max
(4logt + log M)
exp
Mr
Proposition A.4. Given
20 4C2(01) 512x max log d
9 2 max {
[4 + log M).
Mp. Mp.
M2
We have
P [13((T (m) (.))))) 21) - Bell2 (1,,
S
(13)
40
Mt
Proof. Combine the above three lemmas.
h
P
[13((T [1,.k
A1) 8xl12
4x
<P max
1
Je xx)x) 2 Xo(x,
@VD,
rEld]
KT()))
S(((T (m) ()Y) ((supp(3), &
-22)
+P
(14a)
((TT))))) )
p
+P
<
((T(()))
2
2
Mt
Mt
Mt
Mt
16

---

Published in Transactions on Machine Learning Research (07 (07/202) 2023)
B Proof of Lemma 3.4
Recall the definition of central federated Lasso equation
B
1
EM=L
31.(m)
M
Step Set the size of error X >
P
8
Bk 1/ > xx)
(15)
1 M
M
IP
Σ
3 (Tem xpmi)
1
Σ
3k
>X
(16)
M
M
m==
m=1
1
(Te]a (m) (mm)
-Bxc
X
(17)
M
M
3
3/11, > x
(18)
M
m==1
M
3 [t) (Trmee- (mi)) (fmii) - 3/6 -Bal
PP
> MX
(19)
m=1
<TP
Am E [M] |@ (Trmk
11 )
- -3 > xx)
(20)
P (1)3
[4],8 T
80/1, 2x)
(21)
The first inequality is due to the fact that the 4-norm is convex. Ih + (T (m)) - 3 (m) lh <
An application of Jensen's 's
inequality shows that / Em=r (3 (T(m)) x(mi) m())))
X DM ||B (Tom x(m) ) -m6m)) 11. The second inequality is due to the fact that the f--orm is non-negative and an application Pigconhole principle. The third incquality is an application of Boole's incquality, also known as the union bound.
(mm) Txmar
Step 2 The client m sets the size of error X
(m)
P
||
1 be
Bx(1
8x
(22)
4x
minme (M]] Tm(m))
B 8x|1, |1,
<P
(23)
4xmaa
M
(113 (Tihind =/me)) Bx
min [M] h (m)
<
(24)
40max
m=
5
5 ta
<M
(25)
M
The first incquality is due to the fact that tail probability is decrcasing function. The second incquality is due to Step I above. The third inequality is due to is by the deviation inequality of client Teanwork Lasso estimate (lemma& 3.1 by setting the regularization level to be x(m)) (do)² 2p minme[as] h/m)) (6dsg
Step 3. Define "good event"
El NREA {1185.c Sh/1,
h (m))
(26)
4T
The event marks that each central federated Lasso is sufficiently accurate to exclude out sub-optimal arms.
17

---

Published in Transactions on Machine Learning Research (07 (07/2023)
P
(Ei
=P
UkEA {1 :B/|1
})
(27)
4Xmax
k
1 (m)
[1 -
TP
(28)
4xmax
k=1
5K
(29)
The first incquality is an application of Boole's inequality, also known as the union bound. The second inequality is due to Step 2 above.
C Proof of Lemma 3.6
The proof strategy is to use Lemma. E.1 on the dataset S(g.))
Lemma C.1.
Mp
M2p
(1S (12)))
z 4
2 1 t
-exp(p
t).
(30)
36
Proof. We have
[[Mx,1] 2 P(An.
An,+1l P(X, E Un) IVil
8
3
Mp. t
Mp. -1
Thus, Hoeffding inequality indicates that
217
I exp( - 4n7
P(M E[M - n) S expp
[V
In particular, for Mtpp/12 we have
Mp- t) s exp(
M2p2
P(M&, 4
36 t)
Thus, the result follows from the fact that MR.1 S 1(5(),2111
Lemma C.2. For t C3 mine ming Mt (MPp)C2(0)
16
P ( E C supp(3),
/Mp. Φ1
)]
2 Mt
(32)
2v2
Proof. In this case, have sample size at most t and minimal sampling rate Mp. Mp./2.The first is due to ( S and the second due ((S(m) 2 Mp.1/4. Thus, we have
(qp4) 2 Mp./4. By
definition of Cs min, Mt IM CM (0) }. we have the probability bound
TP (((((())))) & c supp((3), VMp. 4:
exp( LM²22C3
2/2
16
(33a)
1
(xgg(-lo((Mtt)) Mt
18

---

Published in Transactions on Machine Learning Research (07 (07/2023)
Lemma C.3. Set (m)
db 3250 V
dMgt CilPalp-t then we have
max reld
S (mm) 12 21 21 Mt
(34)
Proof. In this case, we have minimal sampling rale Mp./2 since / S and (( 2 Mpal/4. Let
X = V
log
V Mp.
exp
Ci(o
| looo
2
M2
Mp
log(dMt)
I exp
- ((())
t. .56
log d
16
4
paCr (0o) Mt
= exp
4M log(dMt) + log
- (log/ / + log M)
< exp
Mt
Lemma C.4. Given 1 1> Cs. We have
PP P( [BB(o (0 )2.) Bxll1 V
logt + log M + log dd
2
p² (0o)
+ 2 2xxp
-2
(36)
pēC1 (do) Mt
Mt
32
Proof. Apply the above three lemmas
P |8
(3(())))
(q (g),k A1) - h
4x
[x(r) 2 do(X, OVP,
<P max
rE|d]
(S(TR))
(((((()))) (4,,)) C(supp(3), Φ V2
-IP
(37a)
P
2
M2p:C2(0)3
(-
M2ppp
22
exp
1)
+exp
+ exp
Mt
16
36
2 Mt
C² (10))
2xxp
M2
32
D Proof of Theorem 3.7
We break the proof into steps.
19

---

Published in Transactions on Machine Learning Research (07/2023)
Step 1. Instantaneous regret. Given Lemma 3.6 if t Cs have
T1+1
22hT B
Σn
I
X. x411
Bs 2 X 11) n Bi
+ 20x
I
LiER
LiER
22hTmmaxx Pr
|1
31
8 Pr
|1 1/
5) + 20x 2Cgoxmaax
2
p² (0o)
=AbTmax
+
2exp
M2
+ 4Co 8²
Mt
32
2 pº (00)
Co logt + log M + log pºC1
=Shrmax (
+ exp
M2
+ 1024
M1
32
M1
32
Cos logt t log M log p²C1
<8hTmaxx (1
2) M
+ 1024
p².²2 (00)
Mt
logt + log M + log d
L1 M
+ L2
Mt
The last inequality is due to exp(-2) < 1/x for all x 0. The constants L1 8bx
32
C²C2())))
and L2 = 1024 Com
P.C,
Step 2. Cumulative Regret of one client.
T
Tt11
(38)
t=
logt + log M + log d
L2
(39)
M
M
t=Co
t=Co
1
L1
log + L2 (log log Md) log
(40)
M
M
1
L1 M
log T.2 log( log T + (log 7)
(41)
M
Step 3. Cumulative regret of all client
M
(m)
RT
Tt
M
Cs
L1
2bx max
log T' + L2 log(Md) log T + L2 (log TT2
M
M
M
m=1
L1 M
-Cr2bxx +
+ Le log(M(d) log + L2(log 2)
=O(log M (log 2)²)
20

---

Published in Transactions on Machine Learning Research (07 /003)
E Supporting Lemmas
Here we state a general version of Lemma 1 in Bastani & Bayati 2020 to facilitate our analysis.
Lemma E.1. (Lasso deviation inequality for non i.i.d. dataset) Given a dataset D with its i.i.d. subdataset
D'. Let () be the Lasso regression estimalor (Definition 1. trained on 'D with regularizalion level X. Suppose the population covariance matria 2 satisfy the compotability condition ((supp(3), Let x > 0 be an error upper bound specified by user. Set X (x.0vD/2) = x (16so)- Then, the 41 estimation error of
((D,)) satisfies the following deviation inequality:
P(II,(D,)) B111 2 x) S <a(x),
(42)
where
a(x) P
max rE[d]
x Xo(x, 2
)x(P)) +P (S(DDD) & C(supp(3) 0 )
+
D
p 2
(43)
F Experiment Details and Additional Experiments
F.1
Synthetic Data
For the baseline case, we set d = 100, K = 5, M = and s = 5, where s is the sparsity level of the parameters that should satisfy 8 < d. The B of each arm for each client is generated by first choosing the possibly nonzero positions for all clients. In our case we randomly choose 10 positions for each arm and the 10 positions are shared across the different clients to represent that the bandit environment faced by different clients are similar (but not exactly the same). We then choose the non-zero elements randomly within the 10 positions of cach arm for each client, and then generate the values from uniform distribution on Jo, 1]. Note that the nonzero values of each arm across different clients are different, and the positions are different too. The covariates of each client are generated from a standard normal distributions independently.
We provide some additional experimental results for different choices of d, K, M in Figure for readers interested in the effect of changing these hyper-parameters in our synthetic data.
F.2 PharmGKB
We utilize the publicly available code for PharmGKB lattps///ithhut hwtph/s../.tub.com/mmmo woamm//hcchr//////e /Warfarin for the processing of the dataset. Specifically, the covariates are generated from either the value in the dataset if it is numerical or from bag-of-word: of all the categories if categorical. Then the covariates are transformed into one-hot encodings and thus the vector is very high-dimensionall (d = 5528). We follow Bastani & Bayali (2020) and classify the different dosages of Warfarin into three classes. [0. 3] is the low-dosage class, [3, 7 is the moderate dosage class, and [7, oo] is the high-dosage class. The reward is defined to be 1 if the correct dosage class is chosen and 0 if not, and we add standard Gaussian noise to the reward. The error rate (in Figure 3) is defined by the number of wrong classifications divided by the total number of classifications.
F.3 Medical MNIST
Neural Network Setting. The fully-connected neural network used to train on the Medical MNIST datasct has the architocture shown in Table 2 where input size is the size of the vectorized image, which is 10800 in our case and oulpul size the number of classes, which is The dataset was randomly split into training set and testing set in the ratio of 9:1. The images pre-processed with random rotation, random horizontal flipping, resizing, center cropping and normalization. The training batch size was 32. The optimizer was SGD with learning rate 0.01 and no momentun or weight decay. The neural network was trained on the training set for 10 epochs and evaluated on the testing set. The final testing classification accuracy was around 99%.
Bandit Setting. The number of arms for each agent is equal the number of classes (6) in this problem. We use the output of the last ReLU layer (ie.., before the last layer) the feature vector for bandit problems,
21

---

Published in Transactions on Machine Learning Research (07/2023)
which means that the feature dimension is 500. At each round, The regret is defined to be whether the feature vector is correctly classified, L.e. the reward is O if the the chosen arm is different from the class of the image and 1 if they are the same. Standard Gaussian noise is added to the reward received by the bandit algorithms.
Table 2: Architecture of the neural network
inlayer: Linear Layer impul size, 4000)
RcLU()
hidden1: Linear (aaer(4400) 2000)
ReLU() hidden2: Lincar Laycr(2000, 1000)
ReLU() hidden3: Lincar Layer(1000, 500) ReLU() outLayer: Linear Layer(500, output size)
22

---

Published in Transactions on Machine Learning Research (07 (07/202) 2023)
2008
(a) M 5,
50
(b) 5,
(c)
200
2000
7000
386
489
200
3065
800
306
483
(d) M 10, = 50
(c) M 10, = 100
(f) M 10, d = 200
630
800
1900
De0tue Halt
D4 0000
M 15,
M 15, 100
(i) M 15, 200
Figure 5: Comparison of the the average cumulative regret per client of the Fedego Fedego Lasso algorithm under different settings of the parameters M, K, d on the synthetic dataset
23


Reviews:
[{"review_id": "86f9lixgX6", "reviewer": "Reviewer_yVoM", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\n1. The paper is well-written, with concise descriptions and theoretical analysis. Both the \"Teamwork\" and \"Selfish\" stages are clear to me.\n\n2. The paper conducts extensive experiments on both synthetic and real datasets to show the effectiveness of the proposed algorithm. The comparison with existing algorithms in Table 1 is very helpful. \n\n**Weakness**\n\n1. While I do see the motivation and effects of the new algorithm design, I suggest a more extensive analysis of how the new algorithm improves compared to Teamwork Lasso and Lasso Bandit. Now there is a paragraph saying the Teamwork Lasso Bandit has privacy leakage by sharing the raw data, but it would be beneficial to analyze the influences of not touching the raw data more thoroughly (e.g., how the performance is influenced?). Also, Figure 3 only compares with Naive Lasso, not the Teamwork Lasso.\n\n2. The paper primarily focuses on linear contextual bandits in federated settings. I wonder whether the approach can extend to other bandit settings. What are the challenges of such extension? \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a new federated bandit policy design named Fedego Lasso for high-dimensional online decision-making. The new policy achieves sublinear regret and preserves the privacy of local clients by only sharing parameter estimates instead of the raw data. The paper provides theoretical guarantees and empirical experiments on synthetic and real datasets.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. A more extensive analysis of how the new algorithm improves compared to Teamwork Lasso and Lasso Bandit.\n\n2. The paper claims that the \"exploration\" process would benefit from all local clients exploring the same arm. Though I see the intuition behind this, will it be a good idea if a proportion of clients explore the same arms? \n\n3. Can we compare with Teamwork Lasso in Figure 3?\n\n", "broader_impact_concerns": "No ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "nKe7G5bGkq", "reviewer": "Reviewer_EENi", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths:\n-   The paper presents rigorous mathematical assumptions and proofs, demonstrating a sound and solid approach to the problem.\n-   The theoretical and empirical results are well-founded and support the effectiveness of the proposed algorithm.\n-   The high-level design of the algorithm is well-explained and easy to understand through the demonstration in Figures 1 and 2.\n\n### Weaknesses:\n-   The primary motivation behind the paper is not entirely clear. Although the paper argues that existing works on federated bandits only protect the local privacy of data but not the local privacy of \"information,\" the definition of local privacy of \"information\" is not well-defined. Therefore, further elaboration on this motivation would be beneficial.\n-   The paper only compares its proposed algorithm with Lasso Bandits in the experimental setting, and other baseline algorithms are not included. It would be useful to add additional baseline algorithms or provide explicit reasoning for the exclusion of other baselines (e.g., different privacy settings).\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper introduces Fedego Lasso, a novel algorithm for the Federated bandits setting that offers sub-linear theoretical regret and preserves local client privacy to safeguard sensitive decision-making information. The proposed approach is supported by both theoretical and empirical analyses, demonstrating its effectiveness in achieving the stated objectives.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "It would be beneficial to emphasize the Lasso estimation technique in the algorithm box to facilitate the reader's understanding without the need to search for the definition of different $\\beta$ in the paper. This would help readers quickly grasp the essence of the algorithm and reduce the cognitive load required to understand it.", "broader_impact_concerns": "As noted in the weakness section, it is essential to provide a more detailed explanation of the local client privacy argument, including a clear definition of what constitutes local privacy \"information\" and why sharing it could be potentially harmful. This clarification is particularly important for readers outside the federated learning community, who may not be familiar with the underlying concepts and implications. By providing a comprehensive explanation, the paper can better contribute to the broader scientific community's understanding of this critical topic.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "TofA86wSEN", "reviewer": "Reviewer_MhHZ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This work has some interesting ideas and is looking at a potentially important problem. However, there are several critical issues associated with the current form of the paper.\n\n(1) Clarity. The paper is very difficult to follow. The figures have a lot of jumping back and forth. The algorithm explanations following each of Alg. 1, 2, 3, and 4 are terrible and do not make much sense. It almost seems that the paper is cut to the current page limitation without thinking about the coherence. As a result, it is very difficult to evaluate.\n\n(2) Communication cost and privacy are not well investigated. The authors made a big deal (repeatedly) about the privacy aspects of the prior works, but failed to present any formal privacy advantage of the proposed solution. The only thing is that communicating model instead of data is \"more private\", which is far from sufficient. As for communication cost, there is always a tradeoff between more communication and better performance, and this aspect is entirely missing.\n\n(3) Lasso and high dimensionality. It is unclear why the lasso regression model is particularly useful for this problem. The authors claimed that this is due to high dimensionality. However, all the analysis does not really use high dimensionality. It is very generic. \n\n(4) Novelty. If $M=1$, does it go back to the known result? It seems the only new thing is to add \"federated lasso model\", i.e., sending local lasso models to server for aggregation, and then sending it back to clients. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies federated lasso bandits with $M$ clients that can both play the linear bandit game in parallel and collaborating through a server to aggretate the lasso model. The design objective is to minimize the cumulative regret while also protecting local information leakage for each client. The proposed algorithm interlaces collaboration phases where the agents work together with individual decision making phases where client only tries to maximize her own reward. The data from the former phase (collaboration) is used to train local lasso models that will be periodically transmitted to the server for aggregation, which will then be sent back to the clients. The algorithm is analyzed and evaluated empirically. ", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The paper must be substantially re-written to clarify the key points. The four concerns in the previous box should all be addressed.", "broader_impact_concerns": "No such need identified. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers are all leaning toward accepting the paper. 

I have a number of comments --- in addition to the reviewers' comments that were addressed by the authors in a revision.

1. As a paper with new technical results, it is missing a technical discussion on what is really new / different in the analysis.  While TMLR's criteria of acceptance does not include novelty, it is still required to properly discuss what is borrowed from related work and what is the "delta". What is new in the regret analysis over Bastani & Bayati (2020) now that you operate in the federated learning case.

2.The discussion w.t.t. (Kim & Paik, 2019; Hao et al., 2020; Oh et al., 2021; Li et al., 2021) is unsatisfactory. While these work is about linear bandits, not contextual linear bandits, one can reduce the problem from this paper to the linear bandits problem by concatenating the  \beta_k into a longer parameter vector, and creating "one-hot" features for each arm. I think a theoretical comparison with respect to these work should be there.   The current discussion sounds like these lasso-bandit-lie methods 

3. The paper emphasizes quite a bit on "privacy protection", "local privacy " and so on, but the definition of "privacy" is not stated clearly. 

4. The presentation and clarity should be improved. For example , ”under data decentralization with a local privacy protection argument.“  What is a "local privacy protection argument"?

I hope the authors could take the chance of a "minor revision" and address the above issues. I believe it will make the paper more impactful.
Decision: Accept (poster)