summaries: This paper studies a setting where Thompson Sampling with greedy approximation oracles is applied to combinatorial semi-bandit. The main contribution is to theoretically reveal how the suboptimality of greedy oracles can affect Thompson sampling in the worst case. Specifically, the greedy regret is shown to be lower bounded by $\Omega(\log T / \Delta^2)$. The authors also prove an almost matching upper bound.   --- After rebuttal ---  I appreciate the authors' kind response. Having read all the responses and review comments, I've found that the result is more significant than I thought. Therefore, I increased my score to 6.

summaries: The paper studies the performance of Thompson-Sampling (TS) when applied to combinatorial multi-armed bandit (CMAB) problems with semi-bandit feedback. It is well known that the combinatorial TS (CTS) algorithm might suffer from linear regret when the combinatorial maximization is solved using an approximation oracle [30]. In this work, the authors apply CTS with a specific family of combinatorial maximization oracles – greedy oracles. They analyze the greedy regret of CTS (which compares the played actions to the greedy solution of the combinatorial problem) and derive regret upper bounds of $O(\log T/\Delta^2)$, where $\Delta$ is a suboptimality gap. They also provide a matching lower bound for CTS on a specific small-scale problem.

summaries: The paper studies the combinatorial multi-armed bandit (CMAB) problem in a setting where exactly solving the corresponding offline optimization problem is not feasible (due to its computational hardness) and the learning agent only has access to a greedy oracle which approximately solves the offline optimization problem. In this framework, the paper analyzes the behavior of a natural variant of the Thompson sampling algorithm called Combinatorial Thompson sampling (CTS). The paper first gives an algorithm-dependent and problem-dependent lower bound showing that CTS faces a fundamental limit, then provides an almost matching upper bound.

summaries: The paper studies the combinatorial semi-bandit problem. It provides the first analysis of Thompson sampling (TS) with the greedy oracle. It shows instances that the TS with Gaussian priors suffers $\Omega(\log T / \Delta^2)$ regret from. It proposes a modified TS with Beta priors and shows that the proposed algorithm achieves $O(\log T / \Delta^2)$ regret for the instances. The proposed algorithm enjoys near-optimal regret for the multi-armed bandit problem.

summaries: The paper presents a TS algorithm that uses Greedy oracle to minimise the cumulative regret on combinatorial multi-armed bandit (CMAB) setting. beside presenting an upper bound, they have also established a lower bound (on the cumulative regret) for their approach. The paper discuss the intuition of behind the proof of their proposed analysis for upper bound assuming the "Greedy" step (Line 4 in  Algorithm 1) returns a unique solution, and then in section 6.2 it relaxes that assumption.  CMAB is a well-known framework in the MAB literature, that generalises probabilistic maximum coverage (PMC), online influence maximization (OIM), multiple-play MAB (MP-MAB), minimum spanning tree (MST) and many others. TS based regret-minimisation algorithms are very efficient for the family of single parameter reward distribution; there are recent studies that apply TS under the CMAB setup. Again, finding the optimal solution (in offline learning) for many problems (like PMC, OIM etc.) is NP-hard. On the other hand, Greedy oracle is a popular choice in various optimisation methods (including submodular maximisation).   Hence, the idea to attack the CMAB setup with TS using a Greedy oracle is very natural.

abstractText: Thompson sampling (TS) has attracted a lot of interest in the bandit area. It was introduced in the 1930s but has not been theoretically proven until recent years. All of its analysis in the combinatorial multi-armed bandit (CMAB) setting requires an exact oracle to provide optimal solutions with any input. However, such an oracle is usually not feasible since many combinatorial optimization problems are NP-hard and only approximation oracles are available. An example [30] has shown the failure of TS to learn with an approximation oracle. However, this oracle is uncommon and is designed only for a specific problem instance. It is still an open question whether the convergence analysis of TS can be extended beyond the exact oracle in CMAB. In this paper, we study this question under the greedy oracle, which is a common (approximation) oracle with theoretical guarantees to solve many (offline) combinatorial optimization problems. We provide a problemdependent regret lower bound of order ⌦(log T/ 2) to quantify the hardness of TS to solve CMAB problems with greedy oracle, where T is the time horizon and is some reward gap. We also provide an almost matching regret upper bound. These are the first theoretical results for TS to solve CMAB with a common approximation oracle and break the misconception that TS cannot work with approximation oracles.

authors:
Milton Abramowitz
Irene A Stegun

title: Handbook of mathematical functions with formulas, graphs, and mathematical tables

authors:
Shipra Agrawal
Navin Goyal

title: Analysis of thompson sampling for the multi-armed bandit problem

venue: In Proceedings of the 25th Annual Conference on Learning Theory,

title: Further optimal regret bounds for thompson sampling

venue: In Proceedings of the 16th International Conference on Artificial Intelligence and Statistics,

authors:
Jean-Yves Audibert
Sébastien Bubeck
Gábor Lugosi

title: Minimax policies for combinatorial prediction games

venue: In Proceedings of the 24th Annual Conference on Learning Theory,

authors:
Peter Auer
Nicolo Cesa-Bianchi
Paul Fischer

title: Finite-time analysis of the multiarmed bandit problem

venue: Machine learning,

authors:
Wei Chen
Yajun Wang
Yang Yuan

title: Combinatorial multi-armed bandit: General framework and applications

venue: In Proceedings of the 30th International Conference on Machine Learning,

authors:
Wei Chen
Yajun Wang
Yang Yuan
Qinshi Wang

title: Combinatorial multi-armed bandit and its extension to probabilistically triggered arms

venue: The Journal of Machine Learning Research,

title: A greedy heuristic for the set-covering problem

venue: Mathematics of operations research,

authors:
Richard Combes
Sadegh Talebi
Alexandre Proutière
Marc Lelarge

title: Combinatorial bandits revisited

venue: In Advances in Neural Information Processing Systems,

authors:
Victor Gabillon
Branislav Kveton
Zheng Wen
Brian Eriksson
S Muthukrishnan

title: Adaptive submodular maximization in bandit setting

authors:
Yi Gai
Bhaskar Krishnamachari
Rahul Jain

title: Combinatorial network optimization with unknown variables: Multi-armed bandits with linear rewards and individual observations

venue: IEEE/ACM Transactions on Networking,

title: Bandit algorithms in information retrieval

venue: Now Publishers,

title: Bandit algorithms in recommender systems

venue: In Proceedings of the 13th ACM Conference on Recommender Systems,

authors:
Alihan Huyuk
Cem Tekin

title: Analysis of thompson sampling for combinatorial multiarmed bandit with probabilistically triggered arms

venue: In Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics,

authors:
Emilie Kaufmann
Nathaniel Korda
Rémi Munos

title: Thompson sampling: an asymptotically optimal finite-time analysis

venue: In Proceedings of the 23rd international conference on Algorithmic Learning Theory,

authors:
David Kempe
Jon Kleinberg
Éva Tardos

title: Maximizing the spread of influence through a social network

venue: In Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,

authors:
Junpei Komiyama
Junya Honda
Hiroshi Nakagawa

title: Optimal regret analysis of thompson sampling in stochastic multi-armed bandit problem with multiple plays

venue: In Proceedings of the 32nd International Conference on International Conference on Machine Learning,

title: On the shortest spanning subtree of a graph and the traveling salesman problem

venue: Proceedings of the American Mathematical society,

authors:
Branislav Kveton
Zheng Wen
Azin Ashkan
Hoda Eydgahi
Brian Eriksson

title: Matroid bandits: fast combinatorial optimization with learning

venue: In Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence,

authors:
Tor Lattimore
Csaba Szepesvári

title: Bandit algorithms

authors:
Shuai Li
Fang Kong
Kejie Tang
Qizhi Li
Wei Chen

title: Online influence maximization under linear threshold model

authors:
Tian Lin
Jian Li
Wei Chen

title: Stochastic online greedy learning with semi-bandit feedbacks

authors:
George L Nemhauser
Laurence A Wolsey
Marshall L Fisher

title: An analysis of approximations for maximizing submodular set functions—i

venue: Mathematical programming,

authors:
Pierre Perrault
Etienne Boursier
Vianney Perchet
Michal Valko

title: Statistical efficiency of thompson sampling for combinatorial semi-bandits

title: Shortest connection networks and some generalizations

venue: The Bell System Technical Journal,

authors:
Matthew Streeter
Daniel Golovin

title: An online algorithm for maximizing submodular functions

venue: In Advances Neural Information Processing Systems,

title: On the likelihood that one unknown probability exceeds another in view of the evidence of two samples

authors:
Qinshi Wang
Wei Chen

title: Improving regret bounds for combinatorial semi-bandits with probabilistically triggered arms and its applications

authors:
Siwei Wang
Wei Chen

title: Thompson sampling for combinatorial semi-bandits

venue: In Proceedings of the 35th International Conference on International Conference on Machine Learning,

authors:
Zheng Wen
Branislav Kveton
Azin Ashkan

title: Efficient learning in large-scale combinatorial semi-bandits

heading: 1 Introduction

text:
Stochastic multi-armed bandit (MAB) problem [20, 5, 3] is a classical online learning framework. It has been extensively studied in the literature and has a wide range of applications [13, 12, 20]. The problem is modeled by a T -round game between the learning agent and the environment. The environment contains an arm set and each arm is associated with a reward distribution. At each round t, the agent first selects an arm, while the environment generates a random reward for each arm from its reward distribution. The agent then obtains the reward of the selected arm. The objective of the agent is to accumulate as many expected rewards over T rounds, or equivalent to minimizing the cumulative expected regret, which is defined as the cumulative difference between the expected reward of the optimal arm and the selected arms over T rounds. To achieve this long-horizon goal, the learning agent has to face the dilemma of exploration and exploitation in each round. The former aims to try arms that have not been observed enough times to get a potentially higher reward, the latter focuses on the arm with the best observed performance so far to maintain a high profit. How to balance the tradeoff between exploration and exploitation is the main focus of the MAB algorithms.
One of the most popular bandit algorithms is the upper confidence bound (UCB) algorithm [5]. The algorithm aims to construct confidence sets for unknown expected rewards and selects arms according to their highest upper confidence bounds. The UCB-type algorithms have been widely studied and provided theoretical guarantees with regret upper bound of order O(log T/ ), where is the
⇤Corresponding author
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
minimum gap between the expected reward of the optimal arm and any suboptimal arms. Thompson sampling (TS) [3, 26] is another popular method to solve MAB problems. It is a randomized algorithm based on the Bayesian idea, which maintains an iteratively updated posterior distribution for each arm and chooses arms according to their probabilities of being the best one. The TS algorithm was introduced in the 1930s [28], but its theoretical analysis is open until recent years [15, 2]. It was proven that the regret upper bound of the TS algorithm is of the same order of O(log T/ ) in MAB problems [3]. Benefited from the advantages of easier implementation and better empirical performance compared to UCB, the TS-type algorithms attract more attentions in recent years.
Despite its importance, the MAB framework may fail to model many real applications since the agent’s action is usually not a single arm but a combination of several arms. This motivates the study on the combinatorial MAB (CMAB) problem [11, 9, 17, 31, 7, 29, 30, 24]. In the CMAB framework, the agent selects a combination of base arms as an action to play in each round. All outcomes of these selected arms are then revealed to the agent, which is called semi-bandit feedback and is widely studied in the literature [7, 29, 32, 30, 14, 24]. Such CMAB framework can cover many real application scenarios including probabilistic maximum coverage (PMC) [6], online influence maximization (OIM) [29], multiple-play MAB (MP-MAB) [17] and minimum spanning tree (MST).
TS-type algorithms have recently attracted a lot of interest in CMAB problems [17, 30, 14, 24]. All of these works need an exact oracle to provide the optimal solution with sampled parameters as input in each round. However, such oracles are usually not feasible since many offline combinatorial optimization problems, such as the offline problem of PMC and OIM [16], are NP-hard and only approximation oracles are available. With an example [30] illustrating the non-convergent regret of TS with an artificial approximation oracle designed for a specific problem instance, whether TS can work well in CMAB problems with common approximation oracles is still an open problem.
One of the most common oracles for offline combinatorial optimization problems with a theoretical guarantee is the greedy algorithm. It sequentially finds the current optimal arm, or the optimal collection of multiple arms according to the structural correlations, to maximize the current total expected reward. When the termination condition is met, it will return the set of all arms found in previous steps as the solution. The termination condition is usually formulated by a constraint on the number of steps. For example, in the PMC, OIM, and MP-MAB problems, such a process is limited to continue K steps. The greedy algorithm can provide approximate solutions for offline problems of PMC [8] and OIM [16], and exact optimal solutions for offline problems of MP-MAB [17] and MST [18]. In general, as long as the expected reward in a problem satisfies the monotonicity and submodularity on the action set, the greedy algorithm serves as an offline oracle to provide an approximate solution [23].
In this paper, we first formulate the CMAB problems with greedy oracle, which is general enough and covers PMC, MP-MAB, and many other problems. In this framework, the objective of the learning agent is to minimize the cumulative greedy regret, defined as the cumulative difference between the expected reward of the selected action and that of the greedy’s solution in the real environment. Focusing on a specific PMC problem instance, we derive the hardness analysis of the TS algorithm with the greedy oracle to solve CMAB problems. Due to the mismatch between the estimation gaps that need to be eliminated by exploration and the actual regret the algorithm needs to pay for each such exploration, the TS algorithm with greedy oracle in this CMAB problem cannot achieve as good theoretical performance as previous MAB algorithms. A problem-dependent regret lower bound of order ⌦(log T/ 2) is provided to illustrate such hardness, where T is the time horizon and is some reward gap. By carefully exploiting the property of the greedy oracle, we also provide an almost matching problem-dependent regret upper bound, which is tight on that PMC problem instance and also recovers the main order of TS when solving MAB problems [3]. These results are the first theoretical results of TS with approximation oracle to solve CMAB problems, which show that the linear regret example in [30] does not hold for every approximation oracle.

heading: 2 Related Work

text:
CMAB problems have been widely studied in the literature [11, 6, 7, 29, 30, 24, 32, 21, 14]. Here we mainly focus on the most relevant works. Gai et al. [11] first study the CMAB problem with linear reward, where the reward of an action is linear in the reward of base arms included in it. They introduce a UCB-type algorithm to solve such problems and allow approximation algorithms to
serve as offline oracles. Later, Chen et al. [6, 7, 29] generalize this framework by considering a larger class of rewards and the case with probabilistically triggered arms (CMAB-T). This framework only assumes the expected reward satisfies the monotonicity and Lipschitz condition on the mean vector of base arms. The combinatorial UCB (CUCB) algorithm is proposed to solve such general CMAB problems, which works with any offline oracle with approximation guarantees. When only approximation oracles are available, the goal of the algorithm is relaxed to minimize the cumulative approximation regret, which is defined as the difference between the expected reward of the selected action and that of the scaled optimal solution. The CUCB algorithm achieves the regret upper bound of order O(log T/ min) [29], where min is the minimum reward gap from the scaled optimal solution over all suboptimal actions.
Compared with UCB-type algorithms which need to compute upper confidence bounds for unknown means of base arms [6, 7, 29], TS-type algorithms do not require the reward function to satisfy the monotonicity on the mean vector of base arms. Benefited from this and other advantages of easier implementation and better practical performances, TS-type algorithms have recently attracted a lot of interest in CMAB problems. Komiyama et al. [17] consider using the TS algorithm to solve the MP-MAB problem, where the agent needs to select K from m arms to maximize the sum of rewards over these selected K arms. They provide an optimal regret upper bound of order O(log T/ K,K+1) for the TS algorithm to solve this problem, where K,K+1 is the reward gap between the K-th and (K + 1)-th optimal arm. Later, Wang and Chen [30] consider using TS to solve more general CMAB problems where only the Lipschitz condition is assumed to be satisfied. Their regret upper bound of order O(log T/ min) matches the main order of the CUCB [29] in the same setting. The coefficient of this upper bound was recently improved by Perrault et al. [24], who study the same CMAB setting. Huyuk et al. [14] extend the analysis of [30] and consider using the TS algorithm to solve the problem of CMAB-T. However, the current regret upper bound is O(1/p⇤) worse than CUCB [29], where p⇤ is the minimum triggering probability.
All of the above TS-based works need an exact oracle to provide the optimal solution with sampled parameters in each round. However, the exact oracles are usually not feasible as many combinatorial optimization problems, such as the offline problem of OIM and PMC, are NP-hard [16]. Wang and Chen [30] have constructed a problem instance and designed an approximation offline oracle for this problem instance. The analysis has shown that the TS algorithm suffers the linear regret of order O(T ) when working with such an approximation oracle. However, this oracle is uncommon and artificial, thus cannot represent the performance of TS when working with common approximation oracles. It is still a significant open problem that whether TS can perform well with approximation oracles.
The greedy algorithm is one of the most important methods with approximation guarantees to solve combinatorial optimization problems. When the mean vector is known beforehand, we call the problem of finding the action with the best expected reward as offline problem. Using the greedy algorithm to solve offline combinatorial problems has been studied for decades, including the problem of shortest spanning subtree [18], shortest connection networks [25], set coverage [8], influence maximization [16], and general submodular optimization [23]. There is also a line of studies considering using greedy to solve online problems [4, 19, 10, 27, 22], some of them require the exact reward function forms as prior knowledge. Among these works the most related to ours is [22], both aiming to solve a general class of online problems. Lin et al. [22] consider using the online greedy strategy to make decisions based on UCB-type estimators. The algorithm sequentially selects a unit to maximize the current expected reward until no feasible unit can be selected in each round. In their setting, a unit conditioned on a set of previously selected units is regarded as an arm and the marginal reward of selecting this unit is the expected reward of this arm. Since the number of combinations of units is usually exponentially large, there is an exponential number of arms to explore, making the algorithm pay exponential memory cost in practical applications. Based on this framework, the algorithm needs to observe the marginal reward after the decision of each step to update the estimate on the arm. However, such observation may be not available as many combinatorial problems treat the action composed of several units as a whole and select them together. Compared to this work, our framework only needs polynomial memory cost and does not require the observation of the marginal reward.
In this paper, we study the problem of CMAB with the common (approximation) greedy oracle and hope to answer the question of whether the TS algorithm can work well in this setting.

heading: 3 Setting

text:
The combinatorial multi-armed bandit (CMAB) problem is formulated by a T -round learning game between the learning agent and the environment. The environment contains m base arms and the arm set is denoted by [m] = {1, 2, . . . ,m}. Each arm i 2 [m] is associated with a distribution Di on [0, 1]. We consider a combinatorial setting where the agent can select several base arms at a time. In many applications, different arms usually have structural correlations in the selection decision of the agent. For example, in the PMC problem, base arms (edges) starting from the same node must be selected together. Thus the base arm set [m] can be further divided into n units, with each unit containing several base arms and a unit of arms will be selected together. Let U be the collection of all units and |s| be the number of base arms contained in unit s for any s 2 U .
In each round t = 1, 2, . . ., the learning agent selects an action St 2 S = {S ✓ U : |S| = K} to play. Here S is the set of all candidate actions containing K units. For any action S, denote [S = {i 2 s for some s 2 S} as the set of base arms that belong to units contained in S. The environment then draws a random output of all base arms Xt = (Xt,1, Xt,2, . . . , Xt,m) from the distribution D = D1 ⇥D2 ⇥ . . .⇥Dm. For any t, Xt,i is independent and identically distributed on Di with expectation µi, for any base arm i. Let µ = (µi)i2[m] be the mean vector. We study the semibandit feedback [30, 7, 29] where the agent can observe feedback Qt = {(i,Xt,i) | i 2 [St}, namely the output of all base arms in units contained in St. Denote Ht = {(S⌧ , Q⌧ ) : 1  ⌧ < t} as the history of observations at time t. The agent finally obtains a corresponding reward Rt = R(St, Xt) in this round, which is a function of action St and output Xt. We assume the expected reward satisfies the following two assumptions, which are standard in CMAB works [7, 30, 14, 24, 29].
Assumption 1. The expected reward of an action S only depends on S and the mean vector µ. That is to say, there exists a function r such that E [Rt] = EXt⇠D[R(St, Xt)] = r(St, µ). Assumption 2. (Lipschitz continuity) There exists a constant B such that for any action S and mean vectors µ, µ 0 , the reward of S under µ and µ 0 satisfies
|r(S, µ) r(S, µ0)|  B X
i2[S |µi µ
0 i| . (1)
When the mean vector µ is known beforehand, finding the optimal action containing K units is called the offline problem. However, the offline problems are usually NP-hard and enumerating all actions to find the best one is not feasible as the number of actions is exponentially large. The Greedy algorithm (presented in Algorithm 1) is a common method to solve such offline problems, which is simple to implement and can provide approximate solutions for OIM [16] and PMC [8], and exact solutions for MP-MAB[17]. More specifically, as long as the reward function satisfies monotonicity and submodularity on the action set, the Greedy algorithm can provide solutions with approximate guarantees [23]. Moreover, the Greedy algorithm is also popular to serve as a heuristic method in real applications and has good practical performance even without a theoretical guarantee.
Algorithm 1 Greedy algorithm 1: Input: base arm set [m] and mean vector µ = (µi)i2[m], unit set U , action size K 2: Initialize: Sg = ; 3: for k = 1, 2, · · · ,K do 4: sk = argmaxs2U\Sg r(Sg [ {s} , µ) 5: Sg = Sg [ {sk} 6: end for 7: Output: Sg
We mainly study the CMAB problem with the Greedy oracle. With input µ = (µi)i2[m], it sequentially selects K units to maximize the current expected reward. To simplify, we assume the Greedy’s solution Sg(µ), abbreviated as Sg , is unique, or equivalently the optimal unit in each step k (Line 4 in Algorithm 1) is unique. The general case with multiple solutions can also be solved and would be discussed later. The objective of the learning agent is to maximize the cumulative expected reward over T rounds, or equivalently to minimizing the cumulative expected regret with respect to the
Greedy’s solution Sg , which we call cumulative greedy regret [22] defined by
Rg(T ) = E " TX
t=1
max {r(Sg, µ) r(St, µ), 0}
# , (2)
where the expectation is taken from the randomness in observations and the online algorithm.
We call Greedy an ↵-approximate oracle if r(Sg(µ0), µ0) ↵ · r(S⇤(µ0), µ0) for any input µ0, where S ⇤(µ0) is the optimal action under µ0. Note when Greedy is ↵-approximate, the upper bound for greedy regret also implies the upper bound for the ↵-approximate regret defined by the cumulative distance between scaled optimal reward ↵ ·r(S⇤(µ), µ) and r(St, µ) over T rounds. The approximate regret is adopted in previous CMAB works based on UCB-type algorithms [7, 29, 32, 21]. It is much weaker than greedy regret as it relaxes the requirements for online algorithms and only needs them to return solutions satisfying the relaxed approximation ratio. We discuss more on challenges in analyzing the ↵-approximate regret with TS-type algorithms in Section 6.1.
An example of CMAB: probabilistic maximum coverage (PMC) The input for the PMC problem is a weighted bipartite graph G = (L,R,E), where each edge (u, v) 2 E is associated with a weight µ(u,v). Denote µ = (µ(u,v))(u,v)2E as the edge weight vector. The goal is to find a node set S ✓ L with |S| = K to maximize the number of influenced nodes in R, where each node v 2 R can be influenced by u 2 S with independent probability µ(u,v). The advertisement placement problem can be modeled by PMC, where L is the web page set, R is the user set and µ(u,v) represents the probability that user v clicks the advertisement on web page u. In this application, the user click probabilities are unknown and need to be learned during iterative interactions. The PMC problem fits our CMAB framework with each edge being a base arm and edges starting from the same node forming a unit. The expected reward of an action S is the expected number of nodes finally influenced by it, which is defined as
r(S, µ) = X
v2R
0 @1 Y
(u,v)2E,u2S
1 µ(u,v)
1
A . (3)
It is proved that the reward function satisfies Assumption 2 [7] and the Greedy oracle can provide an approximate solution with approximation ratio (1 1e ) for any input [23].

heading: 4 Algorithm

text:
In this section, we introduce the combinatorial Thompson sampling (CTS) algorithm with Beta priors and Greedy oracle (presented in Algorithm 2) for CMAB problems.
Algorithm 2 CTS algorithm with Beta priors and Greedy oracle 1: Input: base arm set [m], unit set U , action size K 2: Initialize: 8i 2 [m], ai = bi = 1 3: for t = 1, 2, · · · do 4: 8i 2 [m] : Sample ✓t,i ⇠Beta(ai, bi). Denote ✓t = (✓t,1, ✓t,2, · · · , ✓t,m) 5: Select action St = Greedy([m], ✓t,U ,K) and receive the observation Qt 6: //Update 7: for (i,Xt,i) 2 Qt do 8: With probability Xt,i, Yt,i = 1; with probability 1 Xt,i, Yt,i = 0 9: Update ai = ai + Yt,i, bi = bi + (1 Yt,i) 10: end for 11: end for
The algorithm maintains a Beta distribution with parameters ai and bi for each base arm i 2 [m]. In the beginning, it initializes ai = bi = 1, 8i 2 [m] (Line 2). In each round t, the algorithm first samples a parameter candidate ✓t,i from Beta(ai, bi) representing the current estimate for µi (Line 4). Then the Greedy oracle outputs the solution St according to the input vector ✓t = (✓t,1, ✓t,2, · · · , ✓t,m) (Line 5). Based on the observation feedback, the algorithm then updates the corresponding Beta distributions for observed base arms (Line 7-10).

heading: 5 Lower Bound

text:
We investigate the hardness of the CTS algorithm to solve CMAB problems with Greedy oracle by proving a problem-dependent regret lower bound.
First, we introduce some notations that will be used in the regret analysis. Recall Sg is the solution returned by the Greedy oracle when the input is µ. We denote it as Sg = {sg,1, sg,2, . . . , sg,K}, where sg,k is the k-th selected unit by Greedy. Further, define Sg,k = {sg,1, sg,2, . . . , sg,k} as the sequence containing the first k units for any k 2 [K]. Similarly, let St = {st,1, st,2, . . . , st,K} and St,k = {st,1, st,2, . . . , st,k}. Note Sg,0 = St,0 = ;. The corresponding gaps are defined to measure the hardness of the task and the performance of the algorithm. Definition 1. (Gaps) For any unit s 2 U and index k 2 [K] such that s /2 Sg,k 1, define the marginal reward gap
s,k = r(Sg,k, µ) r(Sg,k 1 [ {s} , µ)
as the reward difference between Sg,k and Sg,k 1 [ {s}. According to the Greedy algorithm, we have s,k > 0 for any k such that s /2 Sg,k. And for any action S 2 S, define S = max {r(Sg, µ) r(S, µ), 0} as the reward difference from the Greedy’s solution Sg . Let
mins = min S2S:s2S S , max s = max S2S:s2S S
be the minimum and maximum reward gap of actions containing unit s, respectively. Denote
max = maxS2S S as the maximum reward gap over all suboptimal actions.
We take the following PMC problem (shown in Figure 1) as the instance to carry out the hardness analysis. Each edge in the graph is a base arm and the set of all outgoing edges from a single node forms a unit. The action size is set to K = 2. The weight µ(u,v) of each edge (u, v) is listed on the edges, where we assume 0 <  0.04. The expected reward r(S, µ) of an action S under µ is defined as Eq (3). For example, when u1 and u2 are selected, the probability of v1 being influenced is 1 (1 µ(u1,v1))(1 µ(u2,v1)) = 0.592 and the probability that v2 is influenced is µ(u2,v2) = 0.3. The expected reward of S = {u1, u2} is r(S, µ) = 0.592 + 0.3 = 0.892. For simplicity, we also assume the output of each base arm in each round is exactly its mean. This assumption still satisfies the above properties and is also adopted in previous lower bound proofs [3] to simplify the analysis.
For convenience, we first list the expected reward of each action in this problem in Table 1. We can find that the greedy solution is Sg = {u2, u1} with sg,1 = u2, sg,2 = u1, and r(Sg, µ) = 0.892, while the optimal action is {u1, u4}. The corresponding marginal reward gaps of each unit can be then computed as follows.
u1,1 = 0.01 ;
u3,1 = , u3,2 = 0.012 + 0.7 ;
u4,1 = 0.02, u4,2 = 0.056 .
In the following, we mainly focus on unit u3 and take it as an example to derive the hardness analysis. According to Table 1, all actions containing u3 are suboptimal actions compared to Sg and minu3 = {u3,u4} = 0.52 +0.008. Thus to avoid regret generation, the algorithm should avoid incorporating u3 in the action St. Intuitively, u3 should be explored at least ⌦ log T/ 2u3,1 = ⌦ log T/ 2 times to be distinguished from sg,1 = u2 and thus can avoid being selected as the first unit by Greedy. However, in each round of exploration for u3, the algorithm needs to pay a constant regret of at least 0.52 + 0.008. Thus the estimation gap needs to be eliminated by exploration on the denominator of ⌦ log T/ 2 cannot be canceled by the actual regret paid in each exploration round.
Such mismatch would cause the greedy regret at least of order ⌦ log T/ 2 .
We give the formal lower bound for both the expected number of selections of each unit and the cumulative greedy regret in the following Theorem 1. Theorem 1. (Lower bound) Using the CTS algorithm with Gaussian priors and Greedy oracle to solve the CMAB problem shown in Figure 1, when T is sufficiently large, we have
E [NT+1,s] = ⌦ log T
2s,1
! , (4)
for any s 6= sg,1 = u2, where NT+1,s = PT
t=1 1{s 2 St} is the number of rounds when s is contained in the selected action set St.
Further, the cumulative greedy regret satisfies
Rg(T ) = ⌦
log T
2u3,1
! = ⌦ ✓ log T
2
◆ . (5)
The proof of Theorem 1 follows directly the intuition of the above hardness analysis. Due to the space limit, we include the detailed proof in Appendix B. The reason why we consider using Gaussian priors to derive the lower bound analysis is that we hope to use its concentration and anti-concentration inequalities. The analysis can directly apply to other types of prior distributions if similar inequalities can be provided. The main operations of CTS with Gaussian priors are very similar to that of Algorithm 2, while the only difference is on the prior distribution for unknown parameters and the corresponding updating mechanism. To be self-contained, we also present the detailed CTS algorithm with Gaussian priors in Appendix B.
Lin et al. [22] also show a lower bound for greedy regret of order ⌦(log T/ 2) with 2 (0, 1/4). However, the problem instance used to derive this lower bound is not a CMAB problem and thus their result is not comparable with Theorem 1.

heading: 6 Upper Bound

text:
By investigating the properties of the CTS algorithm and the Greedy oracle, we also provide a problem-dependent regret upper bound for Algorithm 2 to solve general CMAB problems. Theorem 2. (Upper bound) The cumulative greedy regret of Algorithm 2 can be upper bounded by
Rg(T )  X
s 6=sg,1
max k:s/2Sg,k
6B2 |s|2 maxs log T
( s,k 2B |[Sg| ") 2 +
X
k2[K]
C
"2
✓ C 0
"4
◆|sg,k| max
+ ✓ |[Sg| ✓ 2 + 8
"2
◆ + 4m ◆ max (6)
=O
0 @ X
s 6=sg,1
max k:s/2Sg,k
B 2 |s| 2 max log T
2s,k
1
A , (7)
for any " such that 8s 6= sg,1 and k satisfying s /2 Sg,k, s,k > 2B |[Sg| ", where B is the coefficient of the Lipschitz continuity condition, |[Sg| is the number of base arms that belong to the units contained in Sg , C and C 0 are two universal constants.
Due to the space limit, we provide the proof sketch of Theorem 2 in Section 6.2 and defer the formal proof to Appendix C. In order to better compare the upper and lower bounds, we also analyze the greedy regret of the CTS algorithm with Gaussian priors in Appendix D, which achieves the same order of the upper bound with Theorem 2 only up to some constant factors.

heading: 6.1 Discussions

text:
Challenges in analyzing the ↵-approximate regret with CTS The ↵-approximate regret is first brought up in analyzing UCB-type algorithms [6, 7, 29]. Under UCB, benefiting from the monotonicity between the true parameter µ and the UCB parameter µ̄, the ↵-approximate regret can be deducted as
↵ · r(S⇤, µ) r(St, µ)  ↵ · r(S ⇤ , µ̄) r(St, µ)  r(St, µ̄) r(St, µ)
X
i2[St
|µ̄i µi| ,
where S⇤ 2 argmaxS2S r(S, µ) is an exact optimal action under real parameter µ. Thus it only needs to bound the number of selections of bad action St to get an upper bound for the ↵-approximate regret. However, under CTS, since there is no monotonicity between the true parameter µ and the surrogate parameter ✓, the approximate regret can only be deducted as
↵ · r(S⇤, µ) r(St, µ)  ↵ · r(S ⇤ , µ) ↵ · r(S⇤, ✓) + ↵ · r(S⇤, ✓) r(St, µ)
 ↵ · r(S⇤, µ) ↵ · r(S⇤, ✓) + r(St, ✓) r(St, µ)
 ↵
X
i2[S⇤ |✓i µi|+
X
i2[St
|✓i µi| .
To get an upper bound for the RHS, it requires a sufficient number of selections of the exact optimal action S⇤, which may not be the case with approximate oracles like the example shown in Theorem 1. Thus the ↵-approximate regret may not well fit TS-type algorithms.
Tightness of the upper bound We now discuss the tightness of the regret upper bound in Theorem 2 based on the problem instance shown in Figure 1. Specific to this problem, we have |s|  2 for all s since each node has no more than 2 outgoing edges. And based on [21, Theorem 4], the coefficient of the Lipschitz condition in this problem is B = 1. When 0 <  0.04, we have s,1 = mink:s/2Sg,k s,k for any s 6= sg,1 = u2, and max = {u2,u4} = 0.056 is a constant. Thus our regret upper bound in this problem instance is of order
O
0 @ X
s 6=sg,1
max k:s/2Sg,k
B 2 |s| 2 max log T
2s,k
1
A = O
0 @ X
s2{u1,u3,u4}
log T
2s,1
1 A = O ✓ log T
2
◆ ,
where the last equality holds since u1,1 = 0.01, u4,1 = 0.02 are constants and u3,1 = .
We can see our regret upper bound matches the lower bound of (5) in Theorem 1 only up to some constant factors in this specific problem instance.
Comparison with MAB When each unit contains only one base arm and the action size is K = 1, our CMAB framework recovers the MAB problem and the Greedy oracle can provide the exact optimal solution. Thus we can also compare our regret upper bound with the theoretical results of the TS algorithm in MAB problems. In the MAB problem, the expected reward of each action is exactly the mean of the base arm contained in this action. Thus the Lipschitz coefficient is just B = 1 and |s| = 1 for any unit s. The optimal action is Sg = Sg,1 with |[Sg| = 1. And for any unit s 6= sg,1,
we have maxs = s,1. Thus, according to (6) of Theorem 2, the regret upper bound of Algorithm 2 in MAB problems is of order O ⇣P s 6=sg,1 log T s,1 ⌘ , which recovers the main order of the regret upper bound of TS for MAB problems [3].
Comparison with [22] Though Lin et al. [22] also study greedy regret, the results are not directly comparable in general since the setting studied in [22] is not a CMAB setting. We find that the PMC problem under a bar graph in these two settings can be equivalent, where a bar graph is a special bipartite graph with each left node’s outdegree being 1 (indegree being 0) and each right node’s indegree being 1 (outdegree being 0). In this case, our greedy regret upper bound is of order O(m log T/ 2) and theirs is O(mK log T/ 2). So ours is O(K) better than theirs. Even in this case, their algorithm needs to estimate O(m · 2m) parameters, while Algorithm 2 is more efficient and only needs to estimate O(m) parameters.
The definition of the marginal reward gap Recall that the Greedy oracle provides approximate solutions for problems whose expected reward satisfies monotonicity and submodularity on the action set. Formally, the submodularity means for any action S ✓ T and unit s /2 T , there is r(S [ {s} , µ) r(S, µ) r(T [ {s} , µ) r(T, µ), which characterizes the phenomenon of diminishing returns. One may concern that in these problems, due to the submodularity, the marginal reward gap s,k for larger k may become much smaller and the main order of the upper bound thus blows up. We clarify that the submodularity cannot imply the relationships among marginal reward gaps s,k for different k 2 [K]. The problem instance in Figure 1 satisfying submodularity [16] indicates that the marginal reward gap s,k does not necessarily decrease with the increase of k.

heading: 6.2 Proof Sketch

text:
In this section, we briefly introduce the proof idea of Theorem 2. At any step k 2 [K], for any unit s /2 Sg,k, the selection of s in action St may force the Greedy oracle to choose a worse action in subsequential steps and make CTS suffer constant regret. A sufficient condition for generating zero greedy regret in round t is that each unit st,k selected in step k is actually sg,k for any k 2 [K]. Thus to bound the cumulative greedy regret, we sequentially analyze whether sg,k is appropriately selected at each step k.
Recall that under the framework of the CTS algorithm, the Greedy oracle sequentially selects st,k for k 2 [K] based on ✓t sampled from posterior distributions in round t. Focusing on step k = 1, to ensure st,1 = sg,1, the algorithm needs to guarantee the accurate estimations ✓t,s for any unit s 2 U such that r({s} , ✓t) < r(Sg,1, ✓t), 8s 6= sg,1, where ✓t,s is the projection of ✓t on unit s. We first assume sg,1 is already estimated well. Then based on this assumption, when all of the other units s 6= sg,1 have been explored O(log T/ 2s,1) times and thus estimated accurately, sg,1 would be selected at the first step with high probability. But if after any other unit s 6= sg,1 has already been estimated well, sg,1 is still not selected appropriately, we can conclude that the estimations for sg,1 are not accurate enough. In this case, the Beta posterior for sg,1 tends to be uniformly distributed. When CTS sample ✓t,sg,1 from its Beta posterior, with constant probability there would be r(Sg,1, ✓t) > r({s} , µ) ⇡ r({s} , ✓t) for any unit s 6= sg,1. Thus after some rounds, sg,1 would be selected for enough times and also estimated accurately. In the following rounds, sg,1 would be selected appropriately at the first step with high probability. Above all, the expected number of misselections at the first step can be bounded.
The above analysis can apply to other cases when k = 2, 3, . . . ,K. Based on the correct selections in the first k 1 steps, the misselection of st,k also comes from the bad estimations for both sg,k and other units s /2 Sg,k. To distinguish r(Sg,k 1 [ {s} , ✓t) from r(Sg,k, ✓t), those units need to be explored at least O(log T/ 2s,k) times.
According to the above analysis, for each unit s 6= sg,1, we define the exploration price as
L(s) = O
max
k:s/2Sg,k
log T
2s,k
! . (8)
To avoid being incorrectly selected at some step k, each unit s /2 Sg,k needs to be explored for at least L(s) times. The sum of L(s) over all units s 6= sg,1 leads to the main order of the regret upper bound in Theorem 2.

heading: 6.3 Extension to Multiple-solution Case

text:
We can also extend the analysis of the regret upper bound to the case where multiple solutions may be returned by Greedy with input µ, or equivalently the optimal unit in each step k (Line 4 in Algorithm 1) may not be unique. Let
K = ( {s1, s2, . . . , sK} : s1 2 argmax
s r({s} , µ), . . . , sK 2 argmax s/2{s1,...,sK 1} r({s1, . . . , s} , µ)
)
be the set of all actions that are possibly returned by the Greedy oracle when the input is µ. Here we do not care how Greedy breaks the tie at each step and regard this process as a black box. In order to take into account the worst case where Greedy always returns a solution with minimum reward compared to other possible solutions, we define Sg 2 argminS2 K r(S, µ) as one of Greedy’s possible solutions with the minimum expected reward and consider the cumulative greedy regret defined in Eq (2).
The regret analysis of Algorithm 2 in this case is similar to the proof of Theorem 2. A sufficient condition for generating zero regret in round t is that the selected action St falls into the set K . Thus to bound the cumulative greedy regret, we sequentially analyze whether the unit st,k selected in each step k is an optimal unit conditioned on the previously selected units St,k 1. For completeness, we include the regret upper bound as well as the detailed proof for this case in Appendix E.

heading: 7 Conclusion

text:
In this paper, we aim to answer the question of whether the convergence analysis of TS can be extended beyond exact oracles in the CMAB area. Taking the common offline (approximation) Greedy oracle as an example, we derive the hardness analysis of CTS for CMAB problems based on a constructed CMAB problem instance. When using CTS with Greedy oracle to solve this problem, we find that the algorithm needs to explore at least ⌦(log T/ 2) rounds to distinguish suboptimal units from the optimal unit at some step. However, at least constant regret needs to be paid for each exploration round. The mismatch between the gap to be distinguished and the actually paid regret forces the algorithm to pay the cumulative greedy regret of order ⌦(log T/ 2). We also provide an almost matching problem-dependent regret upper bound for the CTS algorithm with Greedy oracle to solve CMAB problems. The upper bound is tight on the constructed problem instance only up to some constant factors and also recovers the main order of TS when solving MAB problems.
An interesting future direction is to extend the current CMAB framework to the case with probabilistically triggered arms (CMAB-T). The CMAB-T framework can model the OIM problem on general social networks. As shown in [21], using UCB-type algorithms to solve such a problem may face great challenges on the computation efficiency. This problem is expected to be avoided by TS-type algorithms since TS would sample candidate parameters to escape the computation of complicated optimization problems. However, the current proof idea based on each selection step of the Greedy oracle (proof of Lemma 1) cannot directly apply to this setting as different units may probabilistically trigger some common base arms. New proof techniques are required to derive the theoretical guarantee of the TS algorithm with the Greedy oracle in this framework.

heading: Acknowledgement

text: The corresponding author Shuai Li is supported by National Natural Science Foundation of China (62006151, 62076161). This work is sponsored by Shanghai Sailing Program.

title: The Hardness Analysis of Thompson Sampling for Combinatorial Semi-bandits with Greedy Oracle


summaries: This paper examines the game theoretic aspect of federated learning. In the proposed model, the players are strategic and may not provide their data to the learning platform and choose to federate in a small coalition. The authors provide an algorithm to compute the optimal federating arrangement, and also analyze the bound of the price of anarchy in theory.

summaries: The paper studies a coalition formation process in federated learning. When agents form a coalition, they aggregate their learned parameters in the hope of a more accurate result. The paper presented an algorithm to obtain the optimal way of partitioning the agents in coalitions, so that the total weighted error of the agents is minimized. In addtion, the paper also analyzed the price of anarchy and provided upper bounds of it.

summaries: This paper studies price of anarchy (PoA) in federated learning. Following the prior work of Donahue and Kleinberg [2021] which initiate a game theoretic model for federated learning, the authors propose a notion of optimality given the average error rates among agents. Under this notion of optimality, the authors first provide an efficient algorithm to compute the optimal solution, and then give PoA bounds that depend on parameters of settings.

summaries: This paper studies a basic federated learning problem, in which some agents, each one with their own dataset, have to jointly agree on a global model. The paper focuses on the trade-off between stability (enforcing that agents are incentivized to collaborate in the global model) and optimality (maximizing social welfare). The paper studies this trade-off by means of a Price of Anarchy analysis.

summaries: This paper studies the stable coalition in federated learning, where the agents can choose to join one coalition or leave with incentives to minimize their own errors. The paper focuses on the task of mean estimation, where the error has a closed-form solution. The main contributions are: 1. proposing an optimal algorithm to minimize the weighted sum of errors; 2. providing the upper bound on PoA.

abstractText: Federated learning is a distributed learning paradigm where multiple agents, each only with access to local data, jointly learn a global model. There has recently been an explosion of research aiming not only to improve the accuracy rates of federated learning, but also provide certain guarantees around social good properties such as total error. One branch of this research has taken a game-theoretic approach, and in particular, prior work has viewed federated learning as a hedonic game, where error-minimizing players arrange themselves into federating coalitions. This past work proves the existence of stable coalition partitions, but leaves open a wide range of questions, including how far from optimal these stable solutions are. In this work, we motivate and define a notion of optimality given by the average error rates among federating agents (players). First, we provide and prove the correctness of an efficient algorithm to calculate an optimal (error minimizing) arrangement of players. Next, we analyze the relationship between the stability and optimality of an arrangement. First, we show that for some regions of parameter space, all stable arrangements are optimal (Price of Anarchy equal to 1). However, we show this is not true for all settings: there exist examples of stable arrangements with higher cost than optimal (Price of Anarchy greater than 1). Finally, we give the first constant-factor bound on the performance gap between stability and optimality, proving that the total error of the worst stable solution can be no higher than 9 times the total error of an optimal solution (Price of Anarchy bound of 9).

authors:
C. Anglano
M. Canonico
Paolo Castagno
Marco Guazzone
M. Sereno

title: A game-theoretic approach to coalition formation in fog provider federations

venue: Third International Conference on Fog and Mobile Edge Computing (FMEC),

authors:
Elliot Anshelevich
Anirban Dasgupta
Jon Kleinberg
Éva Tardos
Tom Wexler
Tim Roughgarden

title: The price of stability for network design with fair cost allocation

venue: SIAM Journal on Computing,

authors:
Eugene Bagdasaryan
Vitaly Shmatikov

title: Differential privacy has disparate impact on model accuracy, 2019

authors:
Avrim Blum
Nika Haghtalab
Ariel D Procaccia
Mingda Qiao

title: Collaborative pac learning

venue: Advances in Neural Information Processing Systems

authors:
Avrim Blum
Nika Haghtalab
Richard Lanas Phillips
Han Shao

title: One for one, or all for all: Equilibria and optimality of collaboration in federated learning

venue: arXiv preprint arXiv:2103.03228,

authors:
Anna Bogomolnaia
Matthew O. Jackson

title: The stability of hedonic coalition structures

venue: Games and Economic Behavior,

authors:
Debora Caldarola
Massimiliano Mancini
Fabio Galasso
Marco Ciccone
Emanuele Rodolà
Barbara Caputo

title: Cluster-driven graph federated learning over multiple domains

venue: arXiv preprint arXiv:2104.14628,

authors:
Shengbo Chen
Cong Shen
Lanxue Zhang
Yuanmin Tang

title: Dynamic aggregation for heterogeneous quantization in federated learning

venue: IEEE Transactions on Wireless Communications,

authors:
Kate Donahue
Jon Kleinberg

title: Model-sharing games: Analyzing federated learning under voluntary participation

authors:
M. Duan
D. Liu
X. Chen
R. Liu
Y. Tan
L. Liang

title: Self-balancing federated learning with global imbalanced data in mobile systems

venue: IEEE Transactions on Parallel and Distributed Systems,

authors:
Marco Guazzone
Cosimo Anglano
Matteo Sereno

title: A game-theoretic approach to coalition formation in green cloud federations

venue: 14th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing,

authors:
Pengfei Guo
Puyang Wang
Jinyuan Zhou
Shanshan Jiang
Vishal M Patel

title: Multi-institutional collaborations for improving deep learning-based magnetic resonance image reconstruction using federated learning

venue: arXiv preprint arXiv:2103.02148,

title: Incentive mechanism design for federated learning: Hedonic game approach, 2021

authors:
Hadi Jamali-Rad
Mohammad Abdizadeh
Attila Szabo

title: Federated learning with taskonomy for non-iid data

venue: arXiv preprint arXiv:2103.15947,

authors:
Elias Koutsoupias
Christos Papadimitriou

title: Worst-case equilibria

venue: In Annual Symposium on Theoretical Aspects of Computer Science,

authors:
Rajesh Kumar
Abdullah Aman Khan
Jay Kumar
A Zakria
Noorbakhsh Amiri Golilarz
Simin Zhang
Yang Ting
Chengyu Zheng
WenYong Wang

title: Blockchain-federated-learning and deep learning models for covid-19 detection using ct imaging

venue: IEEE Sensors Journal,

authors:
Yassine Laguel
Krishna Pillutla
Jerôme Malick
Zaid Harchaoui

title: A superquantile approach to federated learning with heterogeneous devices

venue: 55th Annual Conference on Information Sciences and Systems (CISS),

authors:
Tra Huong Thi Le
Nguyen H. Tran
Yan Kyaw Tun
Minh N.H. Nguyen
Shashi Raj Pandey
Zhu Han
Choong Seon Hong

title: An incentive mechanism for federated learning in wireless cellular network: An auction approach

authors:
J. Lee
Jaehoon Oh
Yooju Shin
S. Yoon

title: Accurate and fast federated learning via iid and communication-aware

venue: grouping. ArXiv,

authors:
Tian Li
Maziar Sanjabi
Ahmad Beirami
Virginia Smith

title: Fair resource allocation in federated learning, 2019

authors:
Tian Li
Anit Kumar Sahu
Ameet Talwalkar
Virginia Smith

title: Federated learning: Challenges, methods, and future directions

venue: IEEE Signal Processing Magazine,

authors:
W.Y.B. Lim
N.C. Luong
D.T. Hoang
Y. Jiao
Y.C. Liang
Q. Yang
D. Niyato
C. Miao

title: Federated learning in mobile edge networks: A comprehensive survey

venue: IEEE Communications Surveys Tutorials,

authors:
Tao Lin
Sebastian U. Stich
Kumar Kshitij Patel
Martin Jaggi

title: Don’t use large mini-batches, use local sgd, 2018

authors:
Lumin Liu
Jun Zhang
S.H. Song
Khaled B. Letaief

title: Client-edge-cloud hierarchical federated learning

venue: IEEE International Conference on Communications (ICC), Jun 2020. doi: 10.1109/icc40277.2020.9148862. URL http://dx.doi.org/10.1109/icc40277.2020

authors:
H. Brendan McMahan
Eider Moore
Daniel Ramage
Seth Hampson
Blaise Agüera y Arcas

title: Communication-efficient learning of deep networks from decentralized data, 2016

authors:
Lokesh Nagalapatti
Ramasuri Narayanam

title: Game of gradients: Mitigating irrelevant clients in federated learning

venue: Proceedings of the AAAI Conference on Artificial Intelligence,

title: Algorithms, games, and the internet

venue: In Proceedings of the thirty-third annual ACM symposium on Theory of computing,

authors:
Felix Sattler
Klaus-Robert Muller
Wojciech Samek

title: Clustered federated learning: Modelagnostic distributed multitask optimization under privacy constraints

venue: IEEE Transactions on Neural Networks and Learning Systems,

authors:
N. Shlezinger
S. Rini
Y.C. Eldar

title: The communication-aware clustered federated learning problem

venue: IEEE International Symposium on Information Theory (ISIT),

authors:
Akhil Vaid
Suraj K Jaladanki
Jie Xu
Shelly Teng
Arvind Kumar
Samuel Lee
Sulaiman Somani
Ishan Paranjpe
Jessica K De Freitas
Tingyi Wanyan

title: Federated learning of electronic health records to improve mortality prediction in hospitalized patients with covid-19: Machine learning approach

venue: JMIR medical informatics,

authors:
Hao Wang
Hsiang Hsu
Mario Diaz
Flavio P. Calmon

title: To split or not to split: The impact of disparate treatment

venue: in classification,

authors:
Yingda Xia
Dong Yang
Wenqi Li
Andriy Myronenko
Daguang Xu
Hirofumi Obinata
Hitoshi Mori
Peng An
Stephanie Harmon
Evrim Turkbey

title: Auto-fedavg: Learnable federated averaging for multi-institutional medical image segmentation

venue: arXiv preprint arXiv:2104.10195,

authors:
Tao Yu
Eugene Bagdasaryan
Vitaly Shmatikov

title: Salvaging federated learning by local adaptation, 2020

authors:
Weishan Zhang
Tao Zhou
Qinghua Lu
Xiao Wang
Chunsheng Zhu
Haoyun Sun
Zhipeng Wang
Sin Kit Lo
Fei-Yue Wang

title: Dynamic fusion-based federated learning for covid-19 detection

venue: IEEE Internet of Things Journal,

heading: 1 Introduction

text:
Recent advances of machine learning techniques has made it possible to apply powerful prediction algorithms to a variety of domains. However, in real-world situations, data is often distributed across multiple locations and cannot be combined to a central repository for training. For example, consider patient medical data located at hospitals or student educational data at different schools. In each case, the individual agents (hospitals or schools) who hold the data wish to find a model that minimizes their error. However, the data at each location may be insufficient to train a robust model. Instead, the agents may prefer to build a model using data from multiple agents: multiple hospitals or schools. Collectively, the combined data may be able to produce a model with much higher accuracy, providing more powerful predictions to each agent and increasing overall welfare. However, it may be infeasible to transfer the data to some coordinating entity to build a global model: privacy, data size, and data format are all possible reasons that would make transferring data not a reasonable solution.
Federated learning is a novel distributed learning paradigm that aims to solve this problem (McMahan et al. [2016]). Data remains at separate local sites, which individual agents use to learn local model parameters or parameter updates. Then, only the parameters are transferred to the coordinating entity
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
(for example, a technology company), which averages together all of the parameters in order to form a single global model, which all of the agents use. Federated learning is a rapidly growing area of research (Li et al. [2020], Kairouz et al. [2019], Lim et al. [2020]).
However, research has also noted that federated learning, in its traditional form, may not be the best option for each agent (Yu et al. [2020], Bagdasaryan and Shmatikov [2019], Li et al. [2019], Mohri et al. [2019]). In the real world, agents may differ in their true distribution: the true model of patient outcomes at hospital A may differ from the true model at hospital B, for example. If these differences are large enough, federating agents may see their error increase under certain situations, potentially even beyond what they would have obtained with only local learning. For example, a player with relatively few samples may end up seeing its model “torqued” by the presence of a player with many samples. For this reason, agents may not wish to federate with every other potential agent.
Instead, each agent faces a choice: given the costs and benefits of federating with different players, it must determine which of the exponentially many combinations of players it would prefer to federate with. Simultaneously, every other agent is also attempting to identify and join a federating group that it prefers - and agents may have conflicting preferences. Prior work (Donahue and Kleinberg [2021], Hasan [2021]) has formulated this problem as a hedonic game, which each player derives some cost (error) from the coalition they join. The aim of such research has been to identify partitions of players that are stable against deviations, for varying definitions of stability. A hedonic game in general may not have any stable arrangements, so the area’s contributions in the analysis of stability adds valuable insight into the incentives of federating agents.
However, this framework also leaves open multiple game theoretic questions. While the federating agents have individual incentives to reduce their error, society as a whole also has an interest in minimizing the overall error. In the school example, individual schools wish to find coalitions that work well on their own sub-populations, while the overall district or state may have an interest in finding an overall set of coalitions that minimizes the overall error. This analysis of a coalition partition’s overall cost falls under the game theoretic notion of optimality.
One natural question relates to the tension between these two goals: the self-interested goal of the individual actors (stability) and the overall goal of reducing total cost (optimality). Given a that set of self-interested agents has found a stable solution, how far from optimal could it be? This is reflected by the Price of Anarchy of a game, the canonical approach to study optimality and stability jointly (Papadimitriou [2001], Koutsoupias and Papadimitriou [1999]). The Price of Anarchy (PoA) is a ratio where the numerator is equal to the highest-cost stable arrangement and the denominator is equal to the lowest-cost arrangement (the optimal arrangement). It is lower bounded by 1, a bound that it achieves only if all stable arrangements are optimal. A higher Price of Anarchy value implies a greater trade off between stability and optimality, and bounding the Price of Anarchy for a particular game puts a limit on this trade-off. Federated learning is a situation where questions of stability have been analyzed, but to our knowledge there has been no systematic analysis of the Price of Anarchy in a model of federated learning.
The present work: A framework for optimality and stability in federated learning In this work, we make two main contributions to address this gap. First, we provide an efficient, constructive algorithm for calculating an optimal federating arrangement. Secondly, we prove the first-ever constant bound on the Price of Anarchy for this game, showing that the worst stable arrangement is no more than 9 times the cost of the best arrangement.
We begin Section 4 by defining optimality, drawing on a notion of weighted error derived from the standard objective in federated learning literature. The main contribution of this section is an efficient, constructive algorithm for calculating an optimal arrangement, along with a proof of its optimality. However, as demonstrated in Section 5, optimality and stability are not always simultaneously achieved. This section analyzes the Price of Anarchy, which measures how far from optimal the worst stable arrangement can be. First, we demonstrate that the optimal arrangement is not always stable. Next, we show that there exist sub-regions where the Price of Anarchy is equal to 1. Finally, this section proves an overall Price of Anarchy bound of 9, the first constant bound for this game.
It is worth emphasizing that, beyond the Price of Anarchy bound itself, part of the contribution of this work is the optimization and analysis to produce this bound. The proofs for this contribution are modular and illuminate multiple properties about the broader federated learning game under study.
As such, these contributions could be useful for further investigating this model. For example, the modular structure of our proof is what enables us to establish stronger bounds for certain sub-cases.
The results in this paper are theoretical and do not depend on any experiments or code. However, while writing the paper, we found it useful to write and work with code to check conjectures. Some of that code is publicly available at github.com/kpdonahue/model_sharing_games.

heading: 2 Related work

text:
Federated learning As we mentioned previously, federated learning has recently seen numerous advances. In this section, we highlight a few papers in federated learning that are especially related to our work.
The idea that agents might differ in their true models (that data might be generated non-i.i.d. across multiple agents) is commonly acknowledged in the federated learning literature. For example, Yu et al. [2020], Bagdasaryan and Shmatikov [2019] empirically demonstrate that federated learning, and especially privacy-related additions, can cause a wide disparity in error rates. Some techniques have been developed specifically towards this problem. For example, hierarchical federated learning adds an additional layer of hierarchical structure to federated learning, which could be used to reduce latency or to cluster together similar players (Lin et al. [2018], Liu et al. [2020]). Many other works also relate to clustering, such as (Lee et al. [2020], Sattler et al. [2020], Shlezinger et al. [2020], Wang et al. [2020], Duan et al., Jamali-Rad et al. [2021], Caldarola et al. [2021]). Nagalapatti and Narayanam [2021] uses tools from cooperative game theory to selectively combine gradient updates from multiple agents. These works, which tend to be more applied than our work, may also differ in that they analyze situations where additional information is known, such as the data distribution at each location.
Other work aims to improve accuracy rates by selecting acquiring additional data (Blum et al. [2017], Duan et al. [2021]). Some papers specifically analyze federated learning for high-stakes situations such as medical settings (Xia et al. [2021], Guo et al. [2021], Vaid et al. [2021], Kumar et al. [2021], Zhang et al. [2021]). In general, all of these works have the goal of reducing the average error over all federating agents, which we will use to motivate our definition of optimality in later sections.
Game theory in federated learning The closest work to this current paper is our prior paper Donahue and Kleinberg [2021], which we discuss in greater detail in Section 3. Another paper using hedonic game theory to analyze federated learning games is Hasan [2021], which gives conditions for Nash stability in federated learning. Other works analyze the incentives of players to contribute resources towards federated learning: Blum et al. [2021] analyzes fairness and efficiency in sampling additional points for federated learning and Le et al. [2021] analyzes incentives for agents to contribute computational resources in federated learning. Interestingly, multiple works take a game theoretic approach towards coalition formation in cloud computing, but with the aim of minimizing some cost besides error, such as electricity usage Guazzone et al. [2014], Anglano et al. [2018].

heading: 3 Model and assumptions

text:
We assume that there are M total agents (sometimes referred to as players). Each agent i 2 [M ] has drawn ni data points from their true local distribution g(✓i), where ✓i are their true local parameters and g(·) is some true labeling function. A player’s goal is to learn a model with low expected error on its own distribution. If a player opts for local learning, then it uses its local estimate of these parameters g(✓̂i) to predict future data points, obtaining error erri({i}). If a set of players C are federating together, we say that they are in a coalition or cluster together. They combine their local estimates of parameters into a single federated estimate, governed by the weighted average of their parameters:
✓̂C = 1P i2C ni · X i2C ni · ✓̂i (1)
A federating player i obtains error erri(C): note that this value may differ between players in the same coalition. For example, if player j has more samples than player k, then ✓̂C will be weighted more towards player j, meaning that player j will have lower expected error than k.
The weighted average method in Equation 1 is commonly used in federated learning (McMahan et al. [2016]). Because it is the most straightforward method, it is sometimes called “vanilla” federated learning. Alternative ways of federation might involve customizing the model for individuals, as in domain adaptation. For example, Donahue and Kleinberg [2021] models three methods of federation: vanilla (called “uniform”), as well as two models of domain adaptation.
There are multiple reasons why we opted to analyze the federation method in Equation 1 in this work. First of all, this federation method is the most straightforward method, and as such it is the natural candidate to begin analysis. Secondly, this federation method is the most interesting to analyze technically. Domain adaptation serves to increase the incentives of an individual agent to participate in federation: it reduces the tension between an individual’s incentives and the optimal overall arrangement. Because of this, for Price of Anarchy it is more valuable and challenging to explore the case in Equation 1, where incentives are more opposed.

heading: 3.1 Theoretical model of federation from Donahue and Kleinberg [2021]

text:
Federated learning has been the subject of both applied and theoretical analysis; our focus here is on the theoretical side. In addition, for game theoretical reasoning to be feasible, we need a model that gives exact errors (costs) for each player, rather than bounds: these are needed in order to be able to argue that a certain arrangement is optimal, for example.
We opt to use the model developed in our prior work Donahue and Kleinberg [2021], which produces the closed-form error value seen in Lemma 1 below. While we work within this model, we emphasize that Donahue and Kleinberg [2021] asked different questions from this paper’s focus: our prior work focused on developing the federated learning model and analyzing the stability of federating coalitions, while our current work analyzes optimality and Price of Anarchy. Lemma 1 (Lemma 4.2, from Donahue and Kleinberg [2021]). Consider a mean estimation task as follows: player j is trying to learn its true mean ✓j . It has access to nj samples drawn i.i.d. Y ⇠ Dj(✓j , ✏2j ), a distribution with mean ✓j and variance ✏2j . Given a population of players, each has drawn parameters (✓j , ✏2j ) ⇠ ⇥ from some common distribution ⇥. A coalition C federating together produces a single model based on the weighted average of local means (Eq. 1). Then, the expected mean squared error player j experiences in coalition C is:
errj(C) = µeP i2C ni + 2 ·
P i2C,i6=j n 2 i + ⇣P i2C,i 6=j ni ⌘2
P i2C ni 2 (2)
where µe = E(✓i,✏2i )⇠⇥[✏ 2 i ] (the average noise in data sampling) and 2 = V ar(✓i) (the average distance between the true means of players).
Note that Donahue and Kleinberg [2021] also analyzes a linear regression game with a similar cost function, though in this work we will restrict our attention to the mean estimation game.
We use some of the same notion and modeling assumptions as Donahue and Kleinberg [2021]. For example, we use C to refer to a coalition of federating agents and ⇧ to refer to a collection of coalitions that partitions the M agents. We will use NC to refer to the total number of samples present in coalition C: NC = P i2C ni. In a few lemmas we will re-use minor results proven in Donahue and Kleinberg [2021], citing them for completeness.
For technical assumptions, we assume number of samples {ni} is fixed and known by all. We also assume that the parameters µe, 2 are approximately known: in particular, results will depend on whether the number of samples is larger or smaller than the critical threshold µe 2 . We assume that a player does not know anything else about its own true parameters ✓i or the parameters of other players: for example, it does not know the true generating distribution ⇥ or if its true parameters are likely to lie far from the parameters of other players. We assume that each player has a goal of obtaining a model with low expected test error on its personal distribution, and that the federating coordinator is motivated to minimize some notion of total cost, but is otherwise impartial.
Finally, it is worth emphasizing key differences between this current work and Donahue and Kleinberg [2021]. The focus of Donahue and Kleinberg [2021] is defining a theoretical model of federated learning and analyzing the stability of such an arrangement. As such, it focuses solely on individual incentives, rather than overall societal welfare. On this other hand, this current work focuses on
discussions of optimality (overall welfare) and Price of Anarchy. Finally, this paper work is in some ways more general: while some results in Donahue and Kleinberg [2021] only allow players to have two different numbers of samples (“small” or “large”), every result in our work holds for arbitrarily many players with arbitrarily many different numbers of samples. This distinction is a function of the questions analyzed in each paper: questions of stability (as in Donahue and Kleinberg [2021]) are much harder to analyze for players with arbitrarily many different sizes.

heading: 4 Optimality

text:
We will begin with the question of optimality. As motivation, it is useful to consider the objective function of most federated learning papers McMahan et al. [2016]:
min ✓
errw(✓) = MX
i=1
pi · erri(✓) =⇤ 1
P M
i=1 ni
MX
i=1
ni · erri(✓)
While the weights can be any pi > 0, P M
i=1 pi = 1, the ⇤ equality reflects the common setting where they are taken to be the empirical average. In this work, we will take the empirical average as our cost function: Definition 1. A coalition partition ⇧ is optimal if it minimizes the weighted sum of errors across players, as defined below:
fw(⇧) = X
C2⇧ fw(C) =
X
C2⇧
X i2C ni · erri(C)
We will say that a coalition partition ⇧ is in OPT if it achieves minimal cost. Note that multiple partitions may achieve minimal cost, so OPT is a set of partitions.
Because ⇧ is a disjoint partition over the M players, fw(⇧) is simply the error errw(✓) scaled by a constant. Therefore, minimizing fw(⇧) is equivalent to minimizing the weighted average of errors.
Some machine learning papers modify the empirical average objective to achieve other goals. For example, Li et al. [2019], Mohri et al. [2019] consider variants where this goal is re-weighted in order to achieve certain fairness goals. Appendix A discusses other possible cost functions.
All of the above analysis holds for any model of federated learning. Lemma 2, below, gives the specific form of cost for federated learning using the model from Donahue and Kleinberg [2021]. The remaining analysis in this paper will assume this cost function. Proofs for results in this section are given in Appendix B. Lemma 2. Consider a partition ⇧ made up of coalitions {Ci}. Then, using the error form given in Equation 2, the total cost of ⇧ is given by
fw(⇧) = X
C2⇧
⇢ µe + 2 ·NC 2 P i2C n 2 i
NC
The two most common arrangements in machine learning tasks are local learning (which we will denote by ⇡l) and the federation in the grand coalition (⇡g), where all of the players are federating together in a single coalition. However, Lemmas 3 and 4 demonstrate that either of these could perform arbitrarily poorly as compared the cost-minimizing (optimal) arrangement. Lemma 3. 8⇢ > 1, there exists a setting where local learning results in average error more than ⇢ times higher than optimal: fw(⇡l)
fw(OPT ) > ⇢.
Lemma 4. 8⇢ > 1, there exists a setting where federating in the grand coalition results in average error more than ⇢ times higher than optimal: fw(⇡g)
fw(OPT ) > ⇢.
A priori, finding a partition of players that minimizes total cost seems extremely challenging. There are exponentially many options for partitions, and two lemmas above have shown that either of the most common choices could be arbitrarily far from optimal. However, the next section will provide an efficient, constructive algorithm to calculate an optimal partition of players into federating coalitions.

heading: 4.1 Calculating an optimal arrangement

text:
The main contribution of this section is Theorem 1, which gives an algorithm for minimizing the total weighted error of the federating agents. Theorem 1. Consider a set of players {ni}. An optimal partition ⇧ can be created as follows: first, start with every player doing local learning. Then, begin by grouping the players together in ascending order of size, stopping when the first player would increase its error by joining the coalition from local learning. Then, the resulting partition ⇧ is optimal.
Though the algorithm in Theorem 1 is straightforward, proving the optimality of the resulting partition ⇧ requires several sub-lemmas. Each sub-lemma is a building-block that describes certain operations that either increase or decrease total cost. The proof of Theorem 1 largely consists of sequentially using these sub-lemmas in order to demonstrate the optimality of the calculated partition.
Statement and description of supporting lemmas First, Lemma 5 demonstrates a close relationship between movements of players that reduce total cost and movements of players that are in that player’s self-interest (recall that players always wish to minimize their expected error). Specifically, it shows that a player wishes to join a coalition from local learning if and only if that move would reduce total cost for the entire partition. Lemma 5 (Equivalence of player preference and reducing cost). Take any coalition Q and any player j. Then, a player wishes to join that coalition (from local learning) if and only if doing so would reduce total cost. That is,
fw({nj}) + fw(Q) fw({nj} [Q) , errj({nj}) errj({nj} [Q)
Next, Lemma 6 shows that “swapping” the roles of two players (one doing local learning, one federating in a coalition) reduces total cost when the larger player is removed to local learning. Lemma 6 (Swapping). Take any set Q including a player nj > nk, where the player nk is doing local learning. Then, swapping the roles of players k and j always decreases total cost.
fw(Q [ {nj}) + fw({nk}) > fw(Q [ {nk}) + fw({nj})
Lemmas 7 and 8 give results for when players are incentivized to leave or join a particular coalition: they show that such incentives are monotonic in the size of the player. By Lemma 5, these results also show the monotonicity of cost-reducing operations. Note that these lemmas are not equivalent: they differ in whether the reference player j is already in the coalition or not. Lemma 7 (Monotonicity of joining). If a player of size nj would prefer local learning to joining a coalition Q, then any player of size nk nj also prefers local learning to joining the same coalition. That is, for nk nj ,
errj(Q [ {nj}) errj({nj}) ) errk(Q [ {nk}) errk({nk}) Conversely, if a player j wishes to join Q, then any other player of size nk  nj would have also wanted to join. That is, for nj nk,
errj(Q [ {nj})  errj({nj}) ) errk(Q [ {nk})  errk({nk})
Lemma 8 (Monotonicity of leaving). Take any coalition Q. Then, if any player j 2 Q of size nj wishes to leave Q for local learning, then any player of size nk nj also wishes to leave for local learning. That is, for nk nj
errj(Q) errj({nj}) ) errk(Q) errk({nk}) Conversely, if a player j 2 Q of size nj does not wish to leave Q for local learning, then any player k 2 Q of size nk  nj also does not wish to leave. That is, for nk  nj
errj(Q)  errj({nj}) ) errk(Q)  errk({nk})
All of the above lemmas have analyzed situations where a single player is moving between coalitions. Lemma 9 analyzes cases where multiple players are rearranged simultaneously. Specifically, it provides an algorithm for combining together two separate groups (and then removing certain players) that is guaranteed to keep constant or reduce total cost.
Lemma 9 (Merging). Consider two groups of players, P,Q. First, merge together the two groups to form P [Q. Then, remove players from P [Q to local learning, removing them in descending order of size. Stop removing players when the first player would prefer to stay (removing it would increase its error). Then, this overall process maintains or decreases total error. In other words,
fw(Q) + fw(P ) fw({Q [ P} \ L) + X
i2L fw({ni}) (3)
where L is the set of large players removed in descending order of size. The inequality is strict so long as the final structure is not identical to the first, up to renaming of players, and it is not the case that all the players have the exact same size.
The proof of Theorem 1 is given simply by applying the lemmas sequentially to show that any other partition ⇧0 can be converted to the described partition ⇧ through a series of operations that decrease or hold constant total cost.

heading: 5 Price of Anarchy

text:
The previous section defined the “optimality” of a federating arrangement as its average error, and additionally provided an efficient algorithm to calculate a lowest-cost arrangement. Given that much of prior work (Donahue and Kleinberg [2021], Hasan [2021]) has studied the stability of cooperative games induced by federated learning, the next natural question is to study the relationship between stability and optimality. This section analyzes this relationship, using the canonical game theoretic tools of Price of Anarchy and Price of Stability. All proofs for this section are in Appendix C.
First, we will define the notions of stability under analysis, which are all drawn from standard cooperative game theory literature (Bogomolnaia and Jackson [2002]). A partition of players ⇧ is core stable if there does not exist a set of players that all would prefer leave their location in ⇧ and form a coalition together. A partition is individually stable (IS) if there does not exist a single player i that wishes to join some existing coalition C, where all members of C weakly prefer that i join. Our results will primarily use the notion of individual stability.
As a reminder, the Price of Anarchy (PoA) is the ratio between the worst (highest-cost) stable arrangement and the best (lowest-cost) arrangement. The Price of Stability is the ratio of the best stable arrangement and the best overall arrangement (regardless of if it is stable or not) (Anshelevich et al. [2008]). Note that the Price of Stability is 1 when there exists an optimal arrangement that is also stable.
First, we will show that for certain ranges of parameter space, the Price of Anarchy and/or Price of Stability are equal to 1. Specifically, Lemma 10 shows that when all players have relatively few samples (no more than µe 2 each), the grand coalition ⇡g is core stable, implying a Price of (Core) Stability of 1. Recall that µe and 2 are parameters of the federated learning model reflecting the average noise of the data and the average dissimilarity between federating agents, respectively. Lemma 10. For a set of players with ni  µe 2 8i, the grand coalition ⇡g is always core stable.
On the other hand, Lemma 11 shows that when all players have relatively many samples (at least µe 2 each), every core or individually stable arrangement is also optimal, which means that the Price of Anarchy for this situation is 1.
Lemma 11. For a set of players with ni µe 2 8i, any arrangement that is core stable or individually stable is also optimal.
However, it is not the case that either the Price of Stability or Price of Anarchy is always 1. Table 1 contains an example demonstrating this: there exists a simple three-player case where the optimal arrangement is not individually stable. However, the Price of Anarchy value here is quite small, which suggests the prospect that the Price of Anarchy in general could be bounded.
The main result of this section is Theorem 2, which proves a Price of Anarchy bound of 9 for this problem: the cost of the highest stable arrangement is no more than 9 times the cost of the optimal (lowest cost) arrangement. Theorem 2 (Price of Anarchy). Denote ⇧M to be a maximum-cost individually stable (IS) partition and ⇧opt to be an optimal (lowest-cost) partition. Then,
PoA = fw(⇧M )
fw(⇧opt)  9
In Theorem 2, the numerator is the cost of ⇧M , a maximum-cost partition, and the denominator is ⇧opt, an optimal (lowest-cost) partition. Recall that Definition 1 gives the cost of an arrangement as the weighted sum of the errors of the respective players. Therefore, to get an upper bound on the Price of Anarchy, we will upper bound the errors players experience in ⇧M and lower bound on the error players experience in ⇧opt.
Summary of proof technique Again, this section will show how the larger theorem is the result of several lemmas that act as building blocks. In particular, the lemmas will take two separate approaches towards creating the bound. Lemmas of the first type (12, 13, 14) all provide upper or lower bounds on the errors certain players can experience. These conditions depend on the size of the player (how many samples it has) and the size of the group it is federating with (how many samples in total the rest of the coalition has). For example, Lemmas 12 and 13 taken together show that a player with at least µe+ 2
2 2 samples has a worst-case error no more than 2 times its best-case error. The same pair of lemmas give a multiplicative bound of 9 for players with numbers of samples that falls between µe9· 2 and µe+ 2
2 2 . Finally, Lemmas 14 and 13 together give a factor of 7.5 for players with fewer than µe9· 2 samples that are federating with other players of total size at least µe
3· 2 . Taken together, these errors show that, for almost all cases, the highest error a player experiences is no more than 9 times higher than the lowest error it might experience.
The final case that needs to be addressed is when a player of size  µe9· 2 is federating in a group with other players of total size  µe3· 2 . Lemma 15 handles this last case by an argument around stability. Specifically, it shows that any players in such an arrangement can only be stable if all of them are grouped together into a single federating coalition. In the proof of Theorem 2, this result ends up enabling an additive factor to the Price of Anarchy bound, which is absorbed into the other factors for a total Price of Anarchy value of 9.
Statement and description of supporting lemmas Next, we will walk through each lemma specifically. Lemma 12 gives an upper bound of µe
ni on the error any player experiences in ⇧M .
Lemma 12. If ⇧M is a maximum-cost IS partition, then erri(⇧M )  µeni for all players i.
Proof. Because ⇧M is individually stable, every player must get error no more than the error it would receive alone (doing local learning). By Lemma 1 with C = ni, a player with samples ni player gets error µe
ni alone.
Next, Lemma 13 provides lower bounds on the error a player can receive in ⇧opt. It does this by bounding the minimum error a player could get in any arrangement. Again, because the cost of ⇧opt is simply the weighted sum of errors of each individual player, this helps to upper bound the Price of Anarchy. First, Lemma 13 shows that for players with at least µe+ 2
2 2 samples, the lowest possible error it could experience is 12 · µe nj , which is a factor of 2 off from its worst-case error in Lemma 12. For players with fewer samples than µe+ 2
2 2 , Lemma 13 says that the lowest error a player
could experience is 2. This means that the ratio between the two errors is lower than 9 so long as nj µe9· 2 . Therefore, in order to get a factor of 9 bound for the overall Price of Anarchy, we need to handle the case of players with size  µe9· 2 , when players have very few samples. Lemma 13. Consider a player nj and any set of players C. Then, we can lower bound the error player j recieves by federating with C:
errj(C [ {nj}) ( 1 2 · µe nj nj µe+ 2 2 2
2 otherwise
Lemma 14 is the first of two lemmas handling the case of players with very few samples. It shows that, if a player of size  µe3· 2 is federating with a set of players of total size at least µe
3· 2 , it is possible to upper bound on the error of players in ⇧M by 7.5 · 2. Given the lower bound of 2 in Lemma 13, these together show that there is a ratio of 7.5 at most between the error this player experiences in its best and worst-case arrangements. Lemma 14. Consider a player j federating with a coalition C. If the total number of samples NC is at least µe3 2 , then errj(C [ {nj})  7.25 · 2.
However, Lemma 14 does not handle one situation: what if a player of size  µe9· 2 is federating with a group of players of total size  µe3· 2 ? Lemma 15 addresses this last case: it shows that the only such arrangement that is stable is one where all such players are grouped together into a single arrangement. Note that this lemma is itself should not be obvious: it is composed of multiple sub-lemmas which are stated and proved in the appendix. The fact that there can be only one group of such players is used in the Theorem 2 to create an overall bound of 9. Lemma 15. Consider an arrangement of players, all of size  µe3 2 , where at least one player is in a federating cluster where the total mass of its partners is no more than µe3 2 . Then, the only stable arrangement of these players is to have all of them federating together.
The full proof of Theorem 2 uses these lemmas collectively in order to get an overall Price of Anarchy bound of 9, showing that the worst individually stable arrangement has total cost no more than 9 times the optimal cost.

heading: 6 Conclusion

text:
In this work, we have given the first Price of Anarchy bound for a game-theoretic model of federated learning. This bound quantifies a key tension between individual incentives and overall societal goals, answering a key question left open in prior literature. Beyond this bound, we also provide an efficient algorithm to calculate an optimal partition of players into federating coalitions, and have characterized conditions where the Price of Anarchy and/or Price of Stability is equal to 1.
There are multiple fascinating extensions to this work. To begin with, other definitions of societal cost (for example, weighting players’ errors differently) could produce different Price of Anarchy bounds. Additionally, further work could model more sophisticated methods of federation, including models of domain adaptation. Finally, it would be interesting to explore other notions of societal interest. For example, one vein of research is fairness: how are error rates divided among federating players? Questions might revolve around the maximum gap in error rates between players and whether players that contribute more samples are always rewarded with lower error. Beyond these avenues, though, we believe that the broad topic of federated learning will continue to contain multiple useful and interesting research directions.

heading: 7 Ethics and societal impact

text:
Given this work’s focus defining notions of optimality, there are important ethical considerations. In particular, “optimality” can be defined in multiple different ways: Section 4 motivates the definition we use and Appendix A discusses the merits of other definitions. In particular, it is worth emphasizing that “optimality” is a technical term in optimization and game theory which is always with respect to a given objective function and does not imply a more holistic notion of how desirable a certain solution is. For example, an arrangement could be “optimal” and still be unfair in how errors are distributed among players.
Although our methodology is application-agnostic, federated learning is a machine learning tool that could be applied towards positive goals (e.g. predicting patient outcomes at hospitals) or negative goals (e.g. used to surveil and control populations). It is also worth considering, for each application, whether there could be some other approach that would better address the need. For example, it may be worth considering whether approaches aiming at increasing the number of samples available for low-resource agents would do a better job of increasing the benefit of a federated learning solution. It may even be the case that a solution beyond machine learning would be preferable, such as interventions to reduce the need for a predictive model.
Acknowledgments and Disclosure of Funding
This work was supported in part by a Simons Investigator Award, a Vannevar Bush Faculty Fellowship, MURI grant W911NF-19-0217, AFOSR grant FA9550-19-1-0183, ARO grant W911NF19-1-0057, a Simons Collaboration grant, a grant from the MacArthur Foundation, and NSF grant DGE-1650441. We are grateful to the AI, Policy, and Practice working group at Cornell for invaluable discussions.

title: Optimality and Stability in Federated Learning: A Game-theoretic Approach