Communication Bounds for the Distributed Experts Problem

Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 07:14:31

Abstract: In this work, we study the experts problem in the distributed setting where an expert's cost needs to be aggregated across multiple servers. Our study considers various communication models such as the message-passing model and the broadcast model, along with multiple aggregation functions, such as summing and taking the $\ell_p$ norm of an expert's cost across servers. We propose the first communication-efficient protocols that achieve near-optimal regret in these settings, even against a strong adversary who can choose the inputs adaptively.  Additionally, we give a conditional lower bound showing that the communication of our protocols is nearly optimal. Finally, we implement our protocols and demonstrate empirical savings on the HPO-B benchmarks.

Main paper: 
 introduction: 
 Online prediction with expert advice is an indispensable task in many fields, including bandit learning (Auer et al., 2002; Lattimore & Szepesvári, 2020) , online optimization (Shalev-Shwartz et al., 2012; Hazan et al., 2016) , robot control (Doyle et al., 2013) , and financial decision making (Dixon et al., 2020) . The problem involves n experts making individual predictions and receiving corresponding costs on each of T days. On each day, we choose an expert based on the historical costs of the experts on previous days, and we receive the cost of the selected expert on that day. The objective is to compete with the best single expert in hindsight, i.e., to minimize the average regret, which is defined as the additional cost the algorithm incurs against the best expert in a horizon of T days. It is known that the Exponential Weights Algorithm (EWA) and Multiplicative Weight Update (MWU) method achieve an optimal regret of O( log n T ) given all historical information, even in the presence of a strong adversary Arora et al. (2012) . With less information, the exponential-weight algorithm for exploration and exploitation (Exp3) achieves near-optimal regret O( n log n T ) in the adversarial bandit setup, where only the cost of one expert is observed on a single day.For a large number of experts and days, it may not be feasible to run classical low-regret algorithms. Motivated by this, recent work (Srinivas et al., 2022; Peng & Zhang, 2022; Woodruff et al., 2023; Peng & Rubinstein, 2023; Aamand et al., 2023) considers the experts problem in the data stream model, where the expert predictions are typically streamed through main memory, and a small summary of historical information is stored.In this paper, we consider an alternative model in the big data setting, namely, the distributed model, where expert costs are split across s servers and there is a central coordinator who can run a low-regret algorithm. However, communicating with different servers is expensive, and the goal is therefore to design a low communication protocol achieving low regret. A motivating example is a distributed online optimization problem, where different samples are held by different servers, and each expert could correspond to a different model in an optimization problem over the union of the samples as in the HPO-B real-world benchmark (Arango et al., 2021) . In this case, it is natural for the cost of an expert to be the sum of the costs of the expert across all servers. Another example aggregation function could be the maximum across servers; indeed, this could be useful if there is a maximum tolerable cost on the servers which we would like not to exceed. For our lower bounds, we also ask the protocol to be able to at least tell if the cost of the expert it chose on a given day is non-zero; this is a minimal requirement of all existing algorithms, such as MWU or Exp3, which update their data BROADCASTÕ( n R 2 + T s) Õ( n R 2 + T s) Õ( n R 2 + T s) MESSAGE-PASSING - -Ω( n R 2 + T s) Ω( n R 2 + T s) MESSAGE-PASSINGstructure based on such a cost. It is also desirable in applications such as the experts problem where one wants to know if the prediction made was right or wrong.In our setting, there is a coordinator who on each day needs to choose an expert based on historical interactions with s servers. We focus on two widely studied communication models, namely, the message-passing model with two-way communication channels and the broadcast model with a broadcast channel. In the message-passing model, the coordinator initiates a round of interaction with a given server, and the messages exchanged are only seen by the coordinator and that particular server. The coordinator then decides who speaks next and repeats this process. The broadcast model is also commonly studied in practice and in theory. It can be viewed as a model for single-hop wireless networks. In the broadcast model, each message exchanged is seen by all servers as well as the coordinator. We note that the broadcast model was a central communication model studied for clustering in Chen et al. (2016) .We can view each server as a database, where it receives possibly new data each day. The costs of the n experts on a day then correspond to n possibly different functions of the data on that day. We note that the costs may be explicitly given, or may be implicit functions of the data, and if the latter, then they may only need to be computed as needed by the protocol.Our goal is to achieve a near-optimal regret versus communication tradeoff in this setting over a horizon of T days. Given the memory-efficient streaming algorithms of Srinivas et al. (2022) ; Peng & Zhang (2022) and the close connection between streaming algorithms and communication-efficient protocols, one might think that implementing a streaming algorithm in our settings is optimal. While we could run a streaming algorithm, a critical difference here is that the coordinator is not memorybounded, and thus can afford to store a weight for each expert. While it cannot run EWA or MWU, which would require Ω(sn) communication per day, it can run a distributed Exp3 algorithm, which samples a single expert, and thus has low communication, but maintains a weight locally for all n experts using Ω(n) memory. We stress this is not possible in the streaming model.With s servers in the message-passing model and with sum aggregation, a straightforward implementation of EWA achieves an optimal regret O( log n T ) with a trivial communication cost of Õ(nT s). A distributed Exp3 algorithm achieves O( n log n T ) regret with a total communication cost of Õ(T s).Here Õ(f ) denotes f • log O(1) (nT s). A natural question is if these bounds are tight and in general what the optimal regret versus communication tradeoff is.We summarize our results in Table 1 and Table 2 . Our upper bounds hold unconditionally against strong adaptive adversarial cost streams, where an adversary chooses its (distributed) cost vector after seeing the distribution that the algorithm uses to sample experts on that day. Also, with a memory bound on the local servers, our lower bounds hold against weaker oblivious adversarial cost streams, where the loss vectors of all days are fixed in advance. A memory-bound on individual devices, excluding the coordinator, is natural, as one should view the coordinator as a more powerful machine than the individual servers. ) regret with probability 1 -1 poly(T ) using Õ( n R 2 + T s) communication unconditionally against strong adversarial cost streams. • (Lower bound) We prove that in the broadcast and hence also the message-passing model, for both the summation and maximum aggregation functions, in order to achieve R ∈[O( log n T ), O( n log n T)] regret, one needs at least Ω( n R 2 + T s) communication even for oblivious adversarial cost streams, with a memory bound M = O( n sT R 2 +1) on the servers. Additionally, when T = O(poly(log (ns))), we prove an Ω(ns) communication lower bound for achieving subconstant regret with the maximum aggregation function in the message-passing model, which is optimal up to logarithmic factors for such T , and which separates the complexity in broadcast and message-passing models. The Ω(ns) lower bound also holds for larger T but may be suboptimal. • (Evaluation) Empirically, the experiments on the real-world HPO-B benchmark and two synthetic datasets verify that our algorithms achieve near-optimal regret using much less communication than EWA. Their regret is also significantly better than that of Exp3. We also demonstrate that our algorithms work with no assumptions on how the costs are distributed across servers. We have provided the source code in the supplementary material. 
related work: 
 Online learning with expert advice. The Multiplicative Weights Update (MWU) method's first appearance dates back to the early 1950s in the context of game theory Brown & Von Neumann (1950) ; Brown (1951) ; Robinson (1951) . The exact form of MWU is carried out by adding randomness, which efficiently solves two-player zero-sum games (Grigoriadis & Khachiyan, 1995) . Ordentlich & Cover (1998) further proves the optimality of such algorithms under various scenarios. The algorithm has later been adopted in a wide range of applications (Cesa-Bianchi & Lugosi, 2006; Freund & Schapire, 1997; Christiano et al., 2011; Garber & Hazan, 2016; Klivans & Meka, 2017; Hopkins et al., 2020; Ahmadian et al., 2022) , including the experts problem. See the comprehensive survey on MWU by Arora et al. (2012) .Multi-armed bandits. Similar to the experts problem, Multi-armed bandits (MAB) is another fundamental formulation in sequential optimization since its appearance in Thompson 1933 ; Robbins 1952 . Unlike the experts problem, where each expert's cost is revealed each day, MAB limits players to observing only the cost of one expert (arm) each day. Both stochastic and adversarial MAB problems have been studied extensively (Audibert et al., 2009; Garivier & Cappé, 2011; Korda et al., 2013; Degenne & Perchet, 2016; Agrawal & Goyal, 2017; Kaufmann, 2018; Lattimore & Szepesvári, 2020; Auer et al., 2002; Auer, 2002) . As we mainly consider adversarial cost streams, the Exponential-weight algorithm for Exploration and Exploitation (Exp3) and its Upper Confidence Bound (UCB) variant are most relevant due to their effectiveness in achieving near-optimal regret in the presence of adversaries (Auer et al., 2002) . 2016 studies the multi-agent linear bandit problem in a peer-to-peer network where agents share the same group of arms with i.i.d. costs across days. Some works also consider the setup where servers need to compete against each other, which is out of our scope (Anandkumar et al., 2011; Besson & Kaufmann, 2018; Bubeck et al., 2020; Wang et al., 2020) . Different from most of these setups, we make no assumptions on the costs across days and servers.DistributedDistributed functional monitoring. The coordinator-server communication model is also commonly seen in the distributed functional monitoring literature (Cormode et al., 2011; Woodruff & Zhang, 2012; Arackaparambil et al., 2009; Cormode et al., 2012; Chan et al., 2012) , where the goal is to approximate function values, e.g., frequency moments, across streams with minimal communications. We note that the goal of the distributed experts problem is different in that the focus is on expert selection rather than value estimation and the algorithms in the distributed functional monitoring literature, to the best of our knowledge, are not directly useful here. 
preliminaries and notations: 
 We use T to denote the total number of days, n the number of experts, and s the number of servers. l t i,j represents the cost observed at step t for expert i on the j-th server. l denotes an estimate to l and [n] denotes {1, 2, • • • , n}. A word of memory is represented as O(log (nT )) bits and we use Õ(•) to suppress log O(1) (nT s) factors. We refer to the Exponential Weight Algorithm (EWA) and Multiplicative Weights Update (MWU) method interchangeably.In the single server expert problem, each expert e i , i ∈ [n] has its cost l t i ∈ [0, 1] on day t. Based on the history, an algorithm A needs to select one expert e A(t) for each day before the outcome is revealed on that day. The goal for the single server expert problem is to minimize the average regret defined as: R(A) = 1 T T t=1 l t A(t)min i * T t=1 l t i * . In the distributed setting, we have s servers and one coordinator where the cost l t i now depends on costs l t i,j observed locally across all the servers. The coordinator plays the role of selecting the expert for the next day based on any algorithm A of its choice. For each j ∈ [s], the j-th server can receive or compute its cost l t i,j , i ∈ [n] for the i-th expert on day t. The actual cost for the i-th expert on day t is defined asl t i = f (l t i,1 , l t i,2 , • • • , l t i,s), where f (•) is an aggregation function. We assume the costs l t i,j are non-negative. We consider two natural choices of f (•): 1. the summation function l t i = s j=1 l t i,j 2. the maximum/minimum function. We focus on the summation and maximum function l t i = max(l t i,1 , l t i,2 , • • • , l t i,s ) in our paper, as the proposed algorithms can be easily adapted to the minimum function. In the distributed setting, regret is defined as in the single server setup withl t i = f (l t i,1 , l t i,2 , • • • , l t i,s ). Without loss of generality, we normalize l t i ∈ [0, 1], l t i,j ≥ 0. In practice, if l t i ∈ [0, ρ],then the regret will increase by a factor of ρ accordingly. Note that the cost vector for all the experts is observed by the corresponding local server. Furthermore, we explore the distributed experts problem in two different communication models:Message-passing model. For the message-passing model, the coordinator can initiate a two-way private channel with a specific server to exchange messages. Messages can only be seen by the coordinator and the selected server. The coordinator then decides which server to speak to next and repeats based on the protocol.Broadcast model. In the broadcast model, the coordinator communicates with all servers using a broadcast channel. Again, the communication channel can only be initiated by the coordinator.We further assume local servers have a memory bound of M in what they can store from previous days, which is a more practical scenario as discussed in Srinivas et al. (2022) ; Peng & Zhang (2022) .Definition 3.1. (Distributed experts problem with a strong adversary). An algorithm A run by the coordinator makes predictions for T days. On day t:1. A commits to a distribution p t over n experts based on the memory contents of the coordinator on day t. 2. The adversary selects the cost l t i,j on each server after observing p t . 3. A selects an expert according to p t and incurs the corresponding cost. 4. The coordinator updates its memory contents by communicating with servers according to the protocol defined by A.We refer to adversaries that can arbitrarily define the l t i,j with no knowledge of the internal randomness or state of A, as oblivious adversaries. Notice that if we send each of the server's local information to the coordinator each day, then running the Exponential Weight Algorithm on the coordinator gives an optimal O( log n T ) regret for strong adversarial streams. However, the communication cost is a prohibitive Õ(nT s) words.As we will use the Exponential Weights Algorithm (EWA) as a sub-routine, we briefly describe it in Algorithm 1. We have the following regret bound for EWA:Algorithm 1 Exponential Weight Algorithm (EWA) Input: learning rate η; Initialize L 0 i = 0, ∀i ∈ [n]; for t = 1 to T do Sample expert i with probability p(i) ∝ exp (-ηL t-1 i ); Update Li by L t i = L t-1 i + l t i , ∀i ∈ [n];Lemma 3.2. (EWA regret, Arora et al. (2012) ). Suppose n, T, η > 0, t ∈ [T ], and l t ∈ [0, 1] n . Let p t be the distribution committed to by EWA on day t. Then:1 T ( T t=1 ⟨p t , l t ⟩ -min i * ∈[n] T t=1 l t i * ) ≤ log n ηT + η.And with probability at least 1δ, the average regret is bounded by: R(A)≤ log n ηT + η + O( log (n/δ) T ). Thus, taking η = log n T and δ = 1 poly(T ) gives us O( log (nT )) regret with probability at least 1 -1 poly(T ) . In the broadcast model, we propose DEWA-M-P that achieves Õ n T be regret with probability 1 -1 poly(T ) and using only Õ(T (b e + s)) overall communication when the aggregation function is the maximum function. Since all of our protocols use (and require) at least T s communication, the coordinator can figure out the exact cost for the selected expert on each day by querying each of the s servers for that expert's cost on that day. 
dewa-s: 
 We describe DEWA-S in Algorithm 2. The intuition is to obtain an unbiased estimate lt for l t using limited communication and then run EWA based on our estimate. More precisely, we use the following estimator to estimate l t on day t:lt i = n be ( s j=1 α t i,j β t i,j ), where α t i,j are i.i.d. Bernoulli random variables following α t i,j ∼ Bernoulli( be n ), and the β t i,j are sampled from Bernoulli(l t i,j ). Asl t i ∈ [0, 1], l t i,j ≥ 0, Bernoulli(l t i,j) is a valid distribution. We can easily verify that this is an unbiased estimator:E[ lt i ] = E n be ( s j=1 α t i,j β t i,j ) = n be s j=1 E[α t i,j ]E β t i,j = n be s j=1 bel t i,j n = l t i . On each day, we only incur communication cost O s + n i=1 be n t j=1 l t i,j ∈ O(b e + s). Thus, the overall communication cost is O(T (b e + s)).Algorithm 2 DEWA-S Input: learning rate η, sampling budget be;Initialize L0 i = 0, ∀i ∈ [n]; for t = 1 to T do Coordinator chooses expert i with probability p(i) ∝ exp (-η Lt-1 i ); for j = 1 to s doCoordinator initiates private channel with server j; for i = 1 to n do Server j observes cost l t i,j and samples α t i,j ∼ Bernoulli( be n ), β t i,j ∼ Bernoulli(l t i,j ); Server j sends tuples (i, j) to the coordinator if α t i,j = 1, β t i,j = 1 and clears its memory; Coordinator calculates lt i = n be ( s j=1 α t i,j β t i,j ); Update Li by Lti = Lt-1 i + lt i , ∀i ∈ [n];4.3 DEWA-S-P As we are using unbiased estimators instead of actual costs, we only obtain the desired regret with constant probability. In order to achieve near-optimal regret with high probability, we propose DEWA-S-P in Algorithm 3. The idea is to run multiple baseline algorithms in parallel to boost the success probability, where we regard each baseline algorithm as a meta-expert. As each meta-expert has constant success probability, the probability that they all fail is exponentially small in the number of meta-experts. Thus, by running EWA on the meta-experts, we can follow the advice of the best meta-expert and achieve near-optimal regret with high probability.Algorithm 3 DEWA-S-PInput: learning rate ηmeta, sampling budget be, failure rate 1/poly(T );Let K = ⌈log (poly(T ))⌉, initialize K baseline algorithms A k and let L 0 k = 0, k ∈ [K]; for t = 1 to T doCoordinator chooses expert according to A k (t) with probability p(k) ∝ exp (-ηmetaL t-1 k ); Coordinator updates memory states for all A k according to Algorithm 2; Coordinator receives costl t A k (t) = s j=1 l t A k (t),j ; Update all L k by L t k = L t-1 k + l t A k (t) ;More precisely, to obtain 1 -1 poly(T ) success probability, we initiate ⌈log (poly(T ))⌉ meta-experts A k , k ∈ [⌈log (poly(T ))⌉] at the start of the algorithm. Each meta-expert runs its own DEWA-S independently across T days. The cost of the k-th meta-expert on day t is defined to be the cost the expert A k selects on the same day, which is denoted as l t A k (t) . With the definition of the cost for the meta-experts, we can then run EWA on the meta-experts.The meta-level EWA needs to know the actual cost l t A k (t) from the s servers of each meta-expert in order to recover the best meta-expert with 1 -1 poly(T ) success probability. Therefore for DEWA-S-P , on each day, we incur a communication cost of Õ (s + (b e + s) log (poly(T ))) = Õ (b e + s) , and the overall communication is Õ(T (b e + s)).We propose DEWA-M described in Algorithm 4 that achieves a near-optimal regret versus communication tradeoff up to log factors for the maximum aggregation function in the broadcast model. i = Lt-1 i + lt i , ∀i ∈ [n];The intuition of DEWA-M is that for each expert, if we walk through the servers in a random order and only update lt i if we encounter l t i,j > lt i , then with high probability, we only need a small number of updates per expert. This cannot be achieved in the message-passing model due to the fact that broadcasting lt i requires Ω(s) communication per expert. In contrast, no communication is required for broadcasting lt i in the broadcast model. In fact, with probability 1δ, each expert will update at most O(log(s/δ)) times. By setting δ = 1 bepoly(T ) and applying a union bound over our sampling budget b e and number T of days, we have the desired low communication with probability at least 1 -1 poly(T ) . More precisely, we have the following theorem (see detailed proof in § A.1): Theorem 4.1. For a sampling budget b e ∈ [n], with probability 1 -1 poly(T ) , the communication cost for DEWA-M is Õ(T (b e + s)).Even though we have a high probability guarantee with minimal communication, we still only have a constant probability guarantee for achieving optimal regret O( n log n beT ). We can boost the success probability using the same trick as in Algorithm 3 by initiating log (poly(T )) copies of DEWA-M as meta-experts and running EWA on top of them. We refer to the high-probability version as DEWA-M-P . We thus have the following theorem (see detailed proof in § A.2): Theorem 4.2. For a sampling budget b e ∈ [n], with probability 1 -1 poly(T ) , the communication cost for DEWA-M-P is Õ(T (b e + s)). 
formal guarantees: 
 We present formal regret analysis of DEWA-S , DEWA-S-P and DEWA-M-P . We show that DEWA-S can achieve regret R = O( n log n T be ) with probability at least 9/10, DEWA-S-P and DEWA-M-P can achieve regret R = O( n log (nT ) T be) with probability at least 1 -1 poly(T ) . We then give a communication lower bound, which holds even in the broadcast model, for both summation and maximum aggregation functions with a memory bound on the individual servers. It holds for oblivious adversarial cost streams, and thus also for strong adversarial cost streams and the message-passing model. We use the communication lower bound for the ϵ-DIFFDIST problem Srinivas et al. (2022) but adapt it to our setting. By reducing the ϵ-DIFFDIST problem to the distributed experts problem, we prove that any protocol for achieving R regret with constant probability requires total communication at least Ω( n R 2 ). It will follow that DEWA-S and DEWA-M are near-optimal in their communication for all regret values R ∈ [O( log n T ), O( n log n T )].We state our regret upper bounds for DEWA-S in Theorem 5.1, DEWA-S-P in Theorem 5.2 and DEWA-M-P in Theorem 5.3. The detailed corresponding proofs can be found in § A. ) with probability at least 1 -1 poly(T )for the distributed experts problem in the broadcast model with maximum aggregation function and for strong adaptive adversarial cost streams.Since the regret and communication bounds hold with probability at least 1 -1 poly(T ) individually, by a union bound, they both hold with probability at least 1 -1 poly(T ) .Theorem 5.4. Let p < 1 2 be a fixed constant that is independent of the other input parameters, and suppose M = O( n sT R 2 + 1) is an upper bound on the total memory a server can store from previous days. Any algorithm A that solves the distributed experts problem in the broadcast model with the summation/maximum aggregation function with regret R and with probability at least 1p, needs at least Ω( n R 2 ) bits of communication. If the algorithm can also determine, with probability at least 1p, if the cost of the selected expert on each day is non-zero, then it also needs Ω(T s) bits of communication. These lowers bounds hold even for oblivious adversarial cost streams.We present the proof of Theorem 5.4 in § A.6. Additionally, we present an Ω(ns) communication lower bound proof in § A.6 for achieving sub-constant regret with the maximum aggregation function in the message-passing model, which is optimal for T ∈ O(poly(log (ns))). This shows that we cannot do better than naïve EWA in this case, which achieves optimal regret with communication Õ(ns). 
experiments: 
 In this section, we demonstrate the effectiveness of our algorithms on the HPO-B benchmark (Arango et al., 2021) under two setups: 1. Message-passing model with summation aggregation function and 2. Broadcast model with maximum aggregation function. As a black-box hyperparameter optimization benchmark, we can regard different models in the HPO-B benchmark as different experts in the distributed experts problem, and different datasets are distributed across different servers. We further regard each search step, which is random search for all model classes, as one day in our distributed experts problem. The cost vector is then the normalized negative accuracy of models on different The results in Figure 1 , Figure 2 and Table 3 show that our algorithms achieve similar regret as the optimal algorithms (Exp3 and EWA) while having less communication cost. We further use two synthetic datasets to evaluate our algorithms under various scenarios, including dense-cost and sparse-cost. We present the results in § C, which show that our algorithms can achieve near-optimal regret with significantly lower communication cost across all scenarios consistently. 
discussion: 
 In this section, we clarify the motivations and rationalities of maximum aggregation function and the memory bound on the local servers.Maximum aggregation function. We deem that maximum aggregation function is commonly in real-world scenarios, and here we present a concrete scenario. Consider different servers are trying out different hyper-parameters for a learning algorithm over the same set of training examples, while different experts are trying out different algorithms. Instead of pursuing the best model in terms of average loss, we want to select the lowest loss achieved by one set of hyper-parameters to represent the performance of the corresponding model. In this context, a maximum/minimum aggregation function is more appropriate than a summation/average aggregation function.Memory bound. We pose a memory bound on the downstream servers with no memory assumption on the central coordinator. We believe this assumption is practical and provides a novel solution for bounding the communication of a server with itself across multiple days, as needed in our communication context for the following reasons: a key challenge for our lower-bound argument without a memory bound on the servers is that we can no longer reduce from the ϵ-DIFFDIST problem. Note that here we regard the cost vectors received by the servers over a span of days as players in the ϵ-DIFFDIST problem. Thus, communication is required in the reduction even for the same server to itself over different days, and we consider our memory bound as a novel way of bounding such communication. However, with unbounded memory on each server, we would not be able to charge extra communication for a server to store its entire history and thus it can "communicate with itself" as much as it would like across days. We note that our memory constraint is mild, and we believe it is practical. Please refer to § A.6 for a more detailed explanation of our lower-bound proof. We leave the removal of our memory bound as an important future direction.A PROOFS.A.1 THEOREM 4.1In order to prove the communication bounds, we need the following lemma:Lemma A.1. Welzl (2000) . With a randomly permuted sequence S = {a 1 , a 2 , • • • , a n } and γ = 0, if we read from left to right and update γ = a i whenever we encounter a i > γ, define random variable X as the number of times γ has is updated during the process. We have the following results:E 2 X = n + 1Given Lemma A.1, we can then prove our statement.Proof. For any expert on any day, we will first prove that with probability at least 1δ, the servers only need to send the corresponding cost to the coordinator at most O(log (s/δ)) times. By Lemma A.1 with n = s in our setup, for any g ≥ 0, we have:Pr (X > g) = Pr 2 X > 2 g ≤ E 2 X 2 g = s + 1 2 g By setting g = log s+1 δ , we have Pr X < log s+1 δ > 1 -δ. Furthermore, letting δ = 1 bepoly(T ) , we have Pr (X < log ((s + 1)b e poly(T ))) > 1 - 1 b e poly(T ).By a union bound over the b e sampled experts and T days, the above guarantee simultaneously holds for all experts sampled and all days, with probability at least 1 -1/poly(T ). The overall communication is then: with probability at least 1 -1/poly(T ), which concludes the proof.A.3 THEOREM 5.1Proof. Define Lt i = t t ′ =1 lt ′ i , ŵt i = exp (-η Lt-1 i ) i ′ exp (-η Lt-1 i ′ ) . Define ŵt = [ ŵt 1 , • • • , ŵt n ] ⊤ , lt = [ lt 1 , • • • , lt n ]⊤ and η is of our choice. We will first prove thatT t=1 ⟨ ŵt , lt ⟩ -min i * LT i * ≤ log n η + η T t=1 n i=1 ŵt i ( lt i ) 2 Define Φ t = 1 η log n i=1 exp -η Lt iWe have:Φ T -Φ 0 = T t=1 Φ t -Φ t-1 = T t=1 1 η log   n i=1 exp -η Lt-1 i exp -η lt i n i=1 exp -η Lt-1 i   = T t=1 1 η log n i=1 ŵt i exp -η lt i ≤ T t=1 1 η log n i=1 ŵt i 1 -η lt i + 1 2 η 2 ( lt i ) 2 ≤ T t=1 1 η n i=1 -η ŵt i lt i + 1 2 η 2 ŵt i ( lt i ) 2 ≤ - T t=1 ⟨ ŵt , lt ⟩ + η T t=1 n i=1 ŵt i ( lt i ) 2where we used ∀x ≥ 0, e -x ≤ 1x + 1 2 x 2 and ∀x, log (1 + x) ≤ x. As Φ 0 = log n η by definition, we have:log n η + η T t=1 n i=1 ŵt i ( lt i ) 2 ≥ Φ T + T t=1 ⟨ ŵt , lt ⟩ ≥ T t=1 ⟨ ŵt , lt ⟩ -min i * LT i *where the second inequality holds due to the fact that ∀i * ∈ [n]:Φ T = 1 η log n i=1 exp -η Lt i ≥ 1 η log exp -η Lt i * ≥ -Lt i *Now we have:T • E[R] = E α,β T t=1 ⟨ ŵt , l t ⟩ -min i * L T i * = T t=1 E α,β T t=1 ⟨ ŵt , l t ⟩ -min i * L T i * = T t=1 E α,β T t=1 ⟨ ŵt , lt ⟩ -min i * E α,β LT i * ≤ T t=1 E α,β T t=1 ⟨ ŵt , lt ⟩ -E α,β min i * LT i * = E α,β T t=1 ⟨ ŵt , lt ⟩ -min i * LT i *Line 3 is due to lt being independent of ŵt on day t and lt is an unbiased estimator. Line 4 is by Jensen's inequality. We then have:T • E[R] ≤ E T t=1 ⟨ ŵt , lt ⟩ -min i * LT i * ≤ E log n η + η T t=1 n i=1 ŵt i ( lt i ) 2 = log n η + η T t=1 E n i=1 ŵt i ( lt i ) 2 = log n η + η T t=1 E n i=1 ŵt i E[( lt i ) 2 ] ≤ log n η + η T t=1 E n i=1 ŵt i 2n b e = log n η + η 2T n b e Line 5 is by: E      n b e s j=1 α t i,j β t i,j   2    = n 2 b 2 e   s j=1 E (α t i,j β t i,j ) 2 + j̸ =h E[α t i,h α t i,k β t i,h β t i,k ]   = n 2 b 2 e   b e n s j=1 l t i,j + b 2 e n 2 j̸ =h l t i,j l t i,h   ≤ n 2 b 2 e   b e n + b 2 e n 2 ( s j=1 l t i,j ) 2   ≤ 2n b eTake η = be log n 2T n . We then have: O( n log n T be ) and let A k = F be the event that it fails. From Theorem 5.1 we have:E[R] ≤ 2 2nPr(A k = F ) ≤ 1 10Thus, the probability that the best meta-expert achieves regret O( n log n T be ) can be lower bounded by:Pr K k=1 (A k = S) ≥ 1 -( 1 10 ) K ≥ 1 -1/poly(T )By Lemma 3.2, running EWA on top of these meta-experts gives us regret:R = O( n log n T b e ) + O( log (K/δ) T )with probability 1 -1/poly(T )δ (by a union bound). Letting δ = 1/poly(T ) then guarantees anO( n log (nT )T be) regret with probability at least 1 -2 poly(T ) , which concludes the proof.A.5 THEOREM 5.3Proof. For DEWA-M we have a constant probability guarantee to have regret R = O( n log (n) T be ). The proof simply follows from the proof of Theorem 5.1, except that we now have actual cost for the sampled experts instead of unbiased estimates. More specifically, we have:T • E[R] ≤ E T t=1 ⟨ ŵt , lt ⟩ -min i * LT i * ≤ E log n η + η T t=1 n i=1 ŵt i ( lt i ) 2 = log n η + η T t=1 E n i=1 ŵt i ( lt i ) 2 = log n η + η T t=1 E n i=1 ŵt i E[( lt i ) 2 ] ≤ log n η + η T t=1 E n i=1 ŵt i n b e = log n η + η T n b eTake η = be log n T n . We then have:E[R] ≤ 2 n log n T b eSince R > 0, by Markov's inequality we have:Pr R > 20 n log n T b e ≤ E[R] 20 n log n T be ≤ 1 10Thus, with probability at least 9 10 DEWA-M has regret R = O( n log (n) T be ). Since we have initiated log (poly(T )) independent instances of DEWA-M , we have probability at least 1 -1/poly(T ) that one of the instances of DEWA-M achieves regret R = O( n log (n) T be ). By Lemma 3.2, running EWA on top of these meta-experts gives us regret:R = O( n log n T b e ) + O( log (log (poly(T ))/δ) T )with probability 1 -1/poly(T )δ (by a union bound). Let δ = 1/poly(T ). This guarantees anO( n log (nT )T be) regret with probability at least 1 -2 poly(T ) , which concludes the proof.We first define the ϵ-DIFFDIST problem.Definition A.2. (ϵ-DIFFDIST problem, Srinivas et al. ( 2022)). There are T players, and each has n bits of information indexed from1 to n. Let µ 0 = Bernoulli( 1 2 ), µ 1 = Bernoulli( 1 2 -ϵ),we must distinguish between the following two cases:• (Case A). Each index for each player is drawn i.i.d. from µ 0 .• (Case B). An index i ∈ [n] is randomly chosen, then the i-th indexed bit of each player is drawn i.i.d. from µ 1 while other bits of players are all drawn i.i.d. from µ 0 .Lemma A.3. (ϵ-DIFFDIST communication bound, Srinivas et al. (2022) ). The communication complexity of solving the ϵ-DIFFDIST problem with a constant 1p probability under the broadcast model, for any p ∈ [0, 0.5), is Ω( n ϵ 2 ) Note that a lower bound for the broadcast model is also a lower bound for the message-passing model. By regarding different days as servers and bits as cost streams of experts, if we generate bits from either case A or case B, then the algorithm needs to distinguish between case A and case B to obtain regret at most ϵ. We design Algorithm 5 to connect the ϵ-DIFFDIST with the distributed experts problem. Algorithm 5 gives a reduction from ϵ-DIFFDIST, and thus we obtain our lower bound in Theorem 5.4. The additional T s factor is from our requirement that we obtain an approximation to the actual cost for the selected expert on each day. We present the complete proof as follows:Proof.1 We will prove this by showing for R = 1 2+ √ 2 ln (24) and p = 1 4 , Algorithm 5 can indeed solve ϵ-DIFFDIST with probability at least 3 4 . The proof extends naturally to any constant δ, p < 1 2 . We further need R < 1 2(c+1) to make sure 1 2 + ϵ is a valid probability. Let Ĉ be the average cost of A. We will show we can solve the ϵ-DIFFDIST problem in both cases.For case A, Ĉ is just the average of T s i.i.d. coin flips. Thus, by Hoeffding's inequality we have:Pr Ĉ ≤ 1 -Rc 2 = Pr 1 -Ĉ ≥ 1 + Rc 2 ≤ exp (- T sR 2 c 2 2 ) ≤ exp (- c 2 2 ) < 1 3multi-player number-in-hand communication lower bound for set disjointness in Braverman et al. (2013) . To solve the multi-player set disjointness problem with s players, where each player has n bits of informationc j i ∈ {0, 1}, i ∈ [n], j ∈ [s],the communication lower bound is Ω(ns) for the message-passing model.In our problem, in the first case all experts have at least one server that has a cost of 1, i.e., ∃j ∈ [s], ∀i ∈ [n], c j i = 1. In the second case, we have one expert whose cost on every server is 0 while the other experts all have at least one server that has a cost of 1. Then, in the first case, the sets (cost vectors on each server) are disjoint for all coordinates (experts) while in the second case, there exists one coordinate (expert) whose intersection over all sets is non-empty. In the second case, this expert has a maximum cost of 0 while all other experts incur a maximum cost of 1. If we can decide which case we are in, then we solve the set disjointness problem, and thus there is an Ω(ns) communication bound. By copying the same hard instance over T days, it follows that if there exists an algorithm that can achieve sub-constant regret for this distributed experts problem, then the algorithm also solves the above set disjointness problem. We have thus obtained an Ω(ns) communication bound for the maximum aggregation function in the message-passing model. Note that EWA can achieve the optimal regret with Õ(ns) communication if we assume T ∈ O(poly(log (ns))), and therefore we cannot do better than EWA up to logarithmic factors.Although we address a similar topic with Kanade et al. ( 2012), we would like to stress that our setup differs quite significantly. In our setup, the ground truth costs for experts are aggregated across all servers. In contrast, the setup of Kanade et al. ( 2012) restricts the ground truth costs for each expert to be allocated to exactly one server per day. Consequently, our setup is more general since instead of finding out the only server that carries the cost on each day, we also incur additional costs from other servers as well.In addition, Kanade et al. ( 2012) only proves their lower bound for n = 2 while we handle general n. On the other hand, for n = 2, they show a lower bound for adaptive adversaries rather than oblivious adversaries, which is our setting. However, we also make an assumption on the server memory budget for proving lower bounds. In fact, our lower bound directly matches that of Kanade et al. (2012) when n = 2 if we do not require the coordinator or current transcript to dictate who speaks next as the additive T s term is no longer needed. More specifically, we compare in Table 4 for the case when only the coordinator can initiate conversation and in Table 5 for the case when both the coordinator and servers can initiate conversation. Note that we can remove the T s term if the servers are allowed to spontaneously initiate conversation, in which case synchronization between servers on each day is not required. We note that Kanade et al. ( 2012)'s upper bound is not applicable in our setting as it assumes the cost (payoff vector) to be distributed to only one server. At the same time, we allow the cost to be distributed to any number of servers. Thus, their setup is a special case of ours. We note that our bounds also match those of Kanade et al. (2012) in this special case, e.g., our upper bound is also Õ( n R 2 ). In short, our results are incomparable as we allow: 1. Costs to be distributed to any number of servers 2. Any n for the lower-bound proof against oblivious adversaries rather than adaptive adversaries.Evaluation setup. In this section, we evaluate the performance of DEWA-S and DEWA-S-P with the summation aggregation function, and DEWA-M and DEWA-M-P with the maximum aggregation function. We measure the average regrets over the days and total communication costs and compare the performance with EWA when b e = n, and with Exp3 when b e = 1. We further evaluate two cost distributions, namely, the Gaussian and Bernoulli distributions. On each server, the costs of the experts are randomly sampled from these distributions. For the best expert, the costs are sampled from N (0.2, 1) or Bernoulli(0.25), and for the other experts, the costs are sampled from N (0.6, 1) or Bernoulli(0.5). For the summation aggregation, all of the costs are truncated to the range [0, 1] and then divided by the number of servers s. To show the robustness of our protocols under extreme cost conditions, we also evaluate a scenario where the costs are sparsely distributed across the servers, i.e., the cost of an expert is held by one server, and other servers receive zero cost for that expert. To further emphasize the effectiveness of our protocol design in such sparse scenarios, we implement and evaluate the performance of the simplified DEWA-S and DEWA-M and we treat them as BASE-S and BASE-M along with their high probability versions BASE-S-P and BASE-M-P . We describe the detail of the baseline algorithms in the following section. We set the learning rate η = 0.1, the number of servers to be s = 50, the number of experts to be n = 100, and the total days to be T = 10 5 for b e = 1 and to be T = 10 4 for b e = n. We set the sampling budget b s = 2 for BASE-S and BASE-S-P . The experiments are run on an Ubuntu 22.04 LTS server equipped with a 12 Intel Core i7-12700K Processor and 32GB RAM.C.1 BASELINES For baselines to be compared, we use the simplified variants of DEWA-S and DEWA-M , namely BASE-S and BASE-M . More specifically, for BASE-S , instead of sampling according to cost values, BASE-S is set to sample servers uniformly. The estimate of cost l t i is then defined as:lt i = ns b e j α t i,j β t i,j l t i,j ,where α t i,j ∼ Bernoulli( be n ), β t i,j ∼ Bernoulli( 1 s ). This is a good baseline to compare with since lt i is also an unbiased estimator. However, due to the uniform sampling strategy, BASE-S will fail in the sparse setting and require an additional factor of s in the regret while DEWA-S does not suffer from this.For BASE-M , we uniformly sample among servers and take the maximum cost encountered as the estimate of the actual cost l t i . To illustrate the effectiveness of DEWA-M , we enforce that the overall communication cost for BASE-M is close to DEWA-M when b e = 1 or b e = n.In Figure 3 , we first present the regrets of DEWA-S and DEWA-S-P on the Gaussian distribution with the summation aggregation function in the non-sparse setting. As we can see in Figure 3a , with sampling budget b e = 1, DEWA-S achieves much smaller regrets than Exp3. And the protocols' average regrets over t are converging to 0 with increasing t. The regrets of all the protocols are comparable to that of EWA when the sampling budget b e = n, as shown in Figure 3b . However, for the sparse scenario, as shown in Figure 4 , the regrets of DEWA-S and DEWA-S-P are much better than BASE-S and BASE-S-P . When b e = 100, DEWA-S and DEWA-S-P can still achieve comparable performance to EWA in the sparse setting. The results further illustrate that our design is effective and can handle such extremely sparse cost conditions. As expected, the high-probability versions of the protocols consistently achieve lower regret than their constant-probability versions.For the maximum aggregation function, we observe similar results as shown in Figure 5 and Figure 6 . The regrets of DEWA-M and DEWA-M-P are close to EWA when b e = n, and their performance is much better than Exp3 when b e = 1. We also observe that the regrets of BASE-M and BASE-M-P are close to that of DEWA-M and DEWA-M-P in the non-sparse setting. However, their communication costs are much higher than DEWA-M and DEWA-M-P when b e = n, as shown in Table 6 and Table 7 . Consistent with our findings for the summation aggregation function, in the sparse setting, the regrets of BASE-M and BASE-M-P are much higher than DEWA-M and DEWA-M-P . The results illustrate that DEWA-M and DEWA-M-P are not restricted to i.i.d. costs among the servers, and they work well in extremely sparse settings. Thus, we conclude that DEWA-M and DEWA-M-P have wider application scopes.We report our communication costs for constant a probability guarantee in Table 6 and for a high probability guarantee in Table 7 . We use the communication cost of EWA as the baseline (1×), which is Õ(nT s + T s). According to our results, for b e = 1 and b e = n, DEWA-S and DEWA-S-P use much smaller communication than Exp3 and EWA respectively. We also notice that, in the sparse setting, DEWA-M and DEWA-M-P use much smaller communication to achieve near-optimal regret, since DEWA-M and DEWA-M-P can quickly identify the server holding large costs. Although the BASE counterparts achieve comparable communication costs to DEWA-S , DEWA-S-P , DEWA-M , and DEWA-M-P , considering their much larger regret in the sparse setting, DEWA-S , DEWA-S-P , DEWA-M , and DEWA-M-P are more consistent across settings. By increasing b e , the protocols achieve lower regret at the cost of more communication. Users can choose b e according to their regret requirements and communication budget. Even if we set b e = n, the communication costs are still much smaller than that of EWA, but the regret of our algorithms is very close to optimal.In this section, we present our regret and communication on Bernoulli distributed costs. Our regrets are shown in Figure 7 , Figure 8 , Figure 9 , and Figure 10 and our communication costs are presented in Table 8 and Table 9 , which are consistent with our observations for Gaussian distribution. DEWA-S , DEWA-S-P , DEWA-M , and DEWA-M-P all perform well in both non-sparse and sparse scenarios, with near-optimal regrets and much smaller communication costs compared with the EWA. The proof followsSrinivas et al. (2022) with a different model and objective. 
 
 Appendix:  


Decision: This paper studies the experts problem in the distributed setting, where the costs associated with experts are distributed across multiple servers.  The authors give both upper and lower bounds.

The overall sentiment is generally favorable towards acceptance. Most reviewers found the problem under study to be interesting and the results to be reasonable. The authors' response has increased the reviewers' confidence in the paper, particularly by effectively addressing one reviewer's concerns about the various assumptions made, such as a space constraint is needed for proving the lower bound.

Reviews: review: paper_summary: paper_summary: This paper studies the classical experts setting in a new communication-focused model that is motivated by evaluating models when the data points are stored across many different servers.  At a high level, the model is the following.  There are $n$ experts (think of them as different models).  There are $s$ servers, each of which is presumably storing some data.  At time $t$, there is some $l_{i,j}^t$ for the $i$'th expert on server $j$.  The overall loss for expert $i$ at time $t$ is $f(l_{i,1}^t, \dots, l_{i,s}^t)$ for some aggregation function $f$.  Natural choices of the aggregation function, which this paper studies, are the sum, the max, and more generally $\ell_p$-norms.  The distributed nature comes from the fact that we, the coordinator, do not have access to the server-specific losses unless we ask them and so incur a communication cost.  So we might have only partial information about each expert, unless we query all servers for all experts.  And since communication is an important bottleneck, we naturally want to minimize it.  So we have an obvious question: what is the tradeoff between communication and achievable regret?

As the authors point out, there are two obvious algorithms.  First, we could simply ask every server for the loss of every expert in every round.  This would incur $O(ns)$ communication per round, but would allow us to run any standard experts algorithm to get regret $O(\sqrt{\frac{\log n}{T}})$.  On the other hand, we could use a *bandit* algorithm like Exp3 to select a single expert at each time, and query every server for that one expert.  This would incur $O(s)$ communication in each round, but would give regret bounds of $O(\sqrt{\frac{n\log n}{T}})$, i.e., the standard bandit regret bound.  These algorithms would work for any aggregation function, since they collect full information for whatever experts they are considering.  So the natural question is whether it is possible to do better: for example, can we get the communication of the bandit algorithm ($O(s)$ per round) with the regret bound of the expert algorithm ($O(\sqrt{\frac{\log n}{T}})$)?

This paper also distinguishes between two communication models, message-passing and broadcast.  In message-passing, sending a message from the coordinator to a server (or vice versa) has a cost of 1 (or the number of words).  In broadcast, by contrast, we assume that the coordinator and the receiver are on a shared channel, so sending one word to *everyone* costs $1$.  

This paper gives algorithms and some lower bounds for the natural aggregation functions in this model.  At a very high level, in message-passing they can only handle the sum aggregation function, but has regret like the experts setting and communication $O(n+s)$ per round.  So if $n \leq s$, they get the communication of the bandit setting but the regret of the expert setting, getting the best of both worlds.  They also get a similar bound for the max aggregation function, but only in the broadcast communication model.
strength_weakness: strength_weakness: In my opinion, there are two main weaknesses of this paper: some of the motivation and assumptions of the results, and some of the writing.  

- The most interesting (and first) result is for the sum aggregation and the message-passing model, but for the other aggregation functions they need the broadcast model.  And I don't understand the motivation for this model.  They discuss how it is a standard model of a one-hop wireless network, which is totally true, but they don't talk at all about why we might have this kind of distributed expert problem in a one-hop wireless network.  And I can't think of any plausible story for this.  Instead, the obvious motivation is their first one on distributed online optimization, which presumably is happening in a datacenter and so is a natural fit for the message-passing model.  So I found it a bit disappointing that most of their results need a communication model that they do not really justify as being plausible for the problem that they're trying to solve.

- The lower bound makes very strange assumptions.  In particular, it assumes that the memory at each server is bounded by a function that depends *inversely* on both $T$ and the regret $R$.  Why would this be?  I don't understand why there would be any such dependence, particularly as a function of $T$.  If anything, one might imagine the memory *growing* with $T$ (as the stream gets longer we buy more and more space on the server); I certainly don't understand why it would be *shrinking*.

- The writing in this paper is quite poor, in a few different ways.
  - At a high level, the authors do a poor job of explaining what they're trying to do (get expert-style regret bounds with bandit-style communication bounds).  I spent a long time thinking that they were trying to get improved dependence on $T$, rather than changing the dependence on $n$.  I'll note that I usually think of $n$ (the number of experts) as being fixed and $T$ going to infinity, so I personally have never cared too much about the difference in the $n$ dependence between experts and bandits.  It makes sense for $n$ to be large in the distributed online optimization setting, though, so I actually do believe that this is an interesting result.  They just don't explain it well at all.
  - At a more detailed level related to the above point, they basically do not explain or give context to their results at all.  They discuss their results starting on line 73, but basically just say "our results are in Tables 1, 2, and 3".  They don't discuss how we should interpret these bounds at all -- are they good?  bad?  Is there room for improvement?  What's tight and what's not?  How do they relate to non-distributed classical settings?  This is just crazy writing -- I've never seen such a lack of discussion about the results in any paper.  This is one of the main reasons why I found it so hard to understand the importance of the results (see above).  
  - At an even more detailed level, even the results tables are strange.  First, they don't seem to actually prove these bounds anywhere.  Look, for example, at the communication bound in Table 1 for DEWA-S.  As far as I can tell, this bound does not appear in any theorem, corollary, or lemma in the rest of the paper.  Instead, the bound for DEWA-S that they actually prove is Theorem 5.1 for the regret (they don't have a theorem statement about the communication anywhere, although they argue it in Section 4.2).  So there is a mismatch between the bounds in the intro and the bounds in the paper.  Of course, the bounds in the intro can be derived from the bounds that they actually prove, but for some reason they do not actually do this, or discuss why they phrase the bounds in these two different ways.
  - Similarly, if you look at the results table or the theorem statements, since they are hiding logarithmic terms the bounds for the high probability results are identical to the constant probability results.  So what's the point of the constant probability results?  Why not just give the high probability results as your results, and the constant probability algorithms as useful subroutines for the high probability case?
questions: questions: - What is the argument for why the broadcast communication model is reasonable for this particular problem (not other distributed problems)?

- Why does the lower bound assume memory that decreases with $R$ and $T$?  What's the motivation for this, and why is it a plausible and interesting scenario?
limitations: limitations: This is fine.
paper_summary: paper_summary: I reviewed this paper a few years back a few times and declined to review this paper for a while to be fair to the authors. I found the paper’s quality has not improved much (as opposed to the average quality improvement for many recycled theory papers) so I can only give somewhere between borderline and accept vote again this time. I would like to emphasize that contains interesting insights to distributed expert problems and could easily be a solid Neurips work. For example, it considers a very generic setting where the aggregation function is $\ell_p$ for all $p$, and its lower bound that utilizes communication complexity also appears to be quite interesting (as opposed to the standard expert lower bound that relies on anti-concentration). But the writing really makes it difficult to champion the paper.
strength_weakness: strength_weakness: I feel more effort is needed to make this paper a smoother read for both theoreticians and general audience.

Some (writing) issues I found: 

1. It was not even completely clear if this is a multi-arm problem or an expert problem from Sec. 3.1. It looks like an expert problem but the authors mentioned the multi-arm setting quite early on.
For the broadcasting setting, how is cost counted? Number of broadcasts? 
2. Tables 1 to 3 are not really very comprehensible. R is left unexplained but it looks like a tunable parameter related to regret but Table 3 has a bound for R whereas Table 1 and 2 do not have. 
3. Notation like R \in [O(something), O(something)] is not really rigorous as the authors are probably aware themselves. Maybe just be explicit to write down constants, or at least do $O(something) \cap \Omega(something)$. 
4. The lower bound on the space constraint $M$ also seems not carefully thought out, or parameterized in a quite awkward manner. The space has to shrink as the number of servers grows?  

Those are all quite minor stuff so I wish the authors could make some effort to clear them up.
questions: questions: I do not have any questions.
limitations: limitations: Not applicable.
paper_summary: paper_summary: The paper investigates the experts' problem in a distributed context, where the costs associated with experts are distributed across multiple servers. The authors present results for two communication models: the message-passing model and the blackboard model. They explore two aggregation functions: the sum and max of an expert's cost across servers. The paper introduces communication-efficient protocols designed to achieve near-optimal regret in these settings.

The paper considers two communication models: the message-passing model, which involves two-way communication channels, and the blackboard model, which utilizes a broadcast channel. The objective is to balance near-optimal regret and communication efficiency.

The proposed algorithms leverage sampling techniques to approximate the aggregated functions and reduce communication overhead.
strength_weakness: strength_weakness: The paper acknowledges the contributions of Kanade et al. in related works. However, it relegates the discussion of the connection with this work to the appendix. This is somewhat unexpected, as the mentioned work shares a significant relation to the current study, probably more so than other cited literature.

The paper considers two aggregation functions: sum and max. The selection of max, however, seems a bit odd and lacks clear motivation.

The lower bound in this paper requires a limit on the memory the central server can utilize. Such a situation is not common in communication lower bounds. This condition seems to be more characteristic of the lower bounds for streaming algorithms rather than for communication models.
questions: questions: Could you move the discussion comparing your work with the Kanade et al. paper into the main text?

Could you provide more justification for selecting the 'max' function as one of the aggregation functions in your study?
limitations: limitations: N/A
paper_summary: paper_summary: The paper considers a distributed variant of the classical problem of learning with experts, where the cost of each expert needs to be aggregated across different servers. Based on three different aggregation models, i.e., sum, maximum and $\ell\_p$ norm,  the authors propose three different algorithm based on the classical exponential weights algorithm. The authors derive bounds on regret and communication costs of the three proposed algorithms. Authors also derive matching lower bounds to demonstrate optimality of their results. Theoretical results are supplemented by empirical results.
strength_weakness: strength_weakness: The novelty of the paper especially in terms of analysis is limited. The analysis of all the algorithms is largely based on existing results. 

Please refer to the next section for additional questions.
questions: questions: I was a reviewer of this paper during ICML 2024 where I had raised some questions which the authors did not answer. Since the content of the paper is largely similar to the ICML submission of this work, my following questions continue to remain. 

1. Why does the coordinator need to initiate communication? In both the models, it is assumed that the coordinator needs to initiate the communication in each round. This is not a very typical consideration in a distributed setting. Usually, there is uplink channel that the clients can use to communicate whenever they want and downlink channel to broadcast messages to the clients/servers. While it might seem that this is a minor issue, I am not convinced that is the case. Firstly, I think it is reason as to why the communication costs have the $Ts$ term. If the clients can themselves initiate the communication, then these terms go away both in the upper and lower bounds. However, it is important to note that if such a coordination does not exist, then the randomization scheme used for aggregation via maximization does not work, or equivalently incurs a cost of $\mathcal{O}(s + b\_e\log(s/\delta))$ while the lower bound would be independent of $s$. This rather unnatural setting is somehow implicitly important for the algorithm to achieve optimal communication cost in the maximum aggregation model.

2. I think there is misrepresentation of results/implicit assumption in the sum aggregation model, which the authors should highlight. There is an implicit assumption that the loss vectors are sparse, in the sense that loss for any expert is high value only for small set of servers. In the experimental section, the authors claim that their results hold "even under extreme settings of sparse loss vectors" while the truth is their theoretical results hold _only_ for sparse regime. Note that the authors claim that in the sum aggregation model the loss for $i^{\text{th}}$ expert at time $t$ is given as $l_{i}^t = \sum_{j = 1}^{s} l_{i,j}^t$ and that the loss is normalized to ensure $l_{i}^t \in [0,1]$. This implicitly places a constraint that $\sum_{j = 1}^{s} l_{i,j}^t \leq 1$ forcing sparser loss vectors. The sparsity is crucial to obtain the improved communication guarantees. A natural choice for "normalization" (as the authors mention) is to average the total loss, i.e., $l_{i}^t = \frac{1}{s} \sum_{j = 1}^{s} l_{i,j}^t$ to ensure $l_{i}^t \in [0,1]$. This is also something the authors have done in the experiments themselves. While such an averaging step does not change the regret guarantees, it significantly impacts the communication cost as the communication cost is proportional to $b_e \cdot T \cdot \sum_{j = 1}^{s} l_{i,j}^t$. If $l_{i}^t = \frac{1}{s} \sum_{j = 1}^{s} l_{i,j}^t \in [0,1]$ then $ \sum_{j = 1}^{s} l_{i,j}^t \leq s$ implying that the worst case communication cost is $\mathcal{O}(b_e T s)$ as opposed to $\mathcal{O}(T(b_e + s))$. I think this is very important point that the authors have not elaborated upon and can change the significance of the results.
limitations: limitations: Yes.

Comments: title: Thanks for the updates
Response to the authors
Clarifications by Authors
Response to Authors
Clarifications by Authors
comment: Thank you for the response. It is satisfactory. I will maintain my score.
We really thank the reviewer for the effort and time in reviewing as well as bringing insightful suggestions, which we will surely incorporate in the final paper.
Ah I see, that makes sense. Thanks a lot for the clarification. I have updated my score accordingly.
We thank the reviewer for additional feedback. 

The random delay provides randomness to the protocol, so that in each round, there can only be a single random server who can occupy the broadcast channel. Randomness is required to guarantee this upper bound against the strongest adversary. Indeed, otherwise, the adversary can exploit the communication pattern and compromise the correctness of the protocol.  For instance, if we fix the server communication order to be from 1 to s, then the adversary can exploit the pattern by assigning $s$ monotonically increasing cost values to the $s$ downstream servers, which,  because of our fixed ordering, requires $s$ rounds of communications per expert. Thus, the overall communication cost would be $\tilde{\Omega}{(Tns)}$, which is much worse than the optimal communication cost we have if we incorporate randomness in our algorithm by using random delays.
Thank you for your response.

Response to coordinator assumption: The proposed fix seems interesting and should fix the issue. Can the authors please elaborate a bit on why do they need the additional random delay? 

Response to sparsity of aggregation function: I think I misunderstood that $\beta$ will need to be updated accordingly. That should resolve the concern.
We thank the reviewer for additional feedback. 

For **Q1**, we thank the reviewer for acknowledging our theoretical contribution and agree that the broadcast model is mostly brought up in the field of theoretical computer science as a natural, though arguably less practical model. Nevertheless, we hope our derived algorithms can provide insight for settings such as distributed online learning in the satellite communication model, or for abstracting the communication costs that we may be interested in, e.g., the coordinator sends a single message to a router which lists multiple destinations, and we only count the cost incurred at the coordinator.

For **Q2**, yes, the memory bound is $O(\frac{n}{s\log{n}}+1)$ for the smallest regret and $O(\frac{1}{s\log{n}}+1)$ for the largest regret, but note that the memory assumption is only required for our lower bound argument and is only needed for the downstream servers. The reason we pose such a memory bound in our lower bound proof is that the general case (without the memory bound) is a hard communication complexity problem and we currently do not have a solution for the most general case. On the other hand, our memory bound always allows for at least any constant amount of memory for each downstream server, which is practical in scenarios in which the memory budget for each server is limited. We hope our initiation of the study of this problem in this model can inspire further work to close the gap in the fully general setting.
I've read the rebuttal, and have the following comments and questions.

**Q1. Motivation for Broadcast**

I totally agree with the authors that broadcast is a standard model in theoretical computer science; I have certainly written papers in a variety of different broadcast models.  But I still don't really buy it for this particular setting.  In your example of a federated hierarchical system where only the bottom level is broadcast, it seems to me like if that's the actual setting that is motivating this, you should explicitly model it and argue that doing well in the bottom layer is sufficient (maybe because the cost incurred in upper layers is negligible)?  My intuition is that all of the settings discussed in the rebuttal (and the paper) for broadcast "feel" like the stories that theorists tell ourselves in order to focus on the math without thinking too hard about the applications, rather than actual applications or motivations.  And that is, to me, a weakness (although note I still like the paper and think it should be accepted).

**Q2. Lower Bound**

If I understand your rebuttal correctly, you're saying that due to your assumption on $R$ the memory upper bound is really something like $O(n / (s \log n))$ (for the smallest regret) or $O(1/(s\log n) + 1)$ (for the largest regret).  Is that what you're saying?  That makes a little more sense than my initial reaction.  But this still seems to me to be a very strong assumption on the memory (particularly in the large regret case).  Is there some justification for it?  Why should I think that the servers are limited to this much memory?