Communication Bounds for the Distributed Experts Problem
Authors: Zhihao Jia
Qi Pang
Trung Tran
David Woodruff
Zhihao Zhang
Wenting Zheng
Venue: NeurIPS 2024 poster (2024)
Keywords: Online Learning
Communication Bounds
Distributed Experts Problem
Primary area: learning_theory
TL;DR: Towards optimal communication bounds for the distributed expert problem under various scenarios

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.

Communication Bounds for the Distributed Experts Problem
Zhihao Jia Carnegie Mellon University zhihao0cmu. edu
Qi Pang Carnegie Mellon University qipang@cmu. edu
Trung Tran University of Pittsburgh tbt8@pitt. edu
David Woodruff
Zhihao Zhang
Wenting Zheng
Carnegie Mellon University dwoodruf@cs cmu.
Carnegie Mellon University zhihaoz38cs cmu. edu
Carnegie Mellon University wentingScmu. edu
Abstract
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 pesssage-passingg model and the broad- cast model, along with multiple aggregation functions, such as summing and taking the Ep norm of an expert's '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 the HPO-B benchmarks.
Introduction
Online prediction with expert advice is an indispensable task in many fields, including bandit learning (Auer et al., [0022 Lattimore & Szepesvári] (200)), online optimization Shalev-Shwarre al.] 2012)
Hazan et al. 20166, robot control (Doyle 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, 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, defined as the additional cost the algorithm incurs against the best expert in a horizon T days. known that the Exponential Weights Algorithm (EWA) and Multiplicative Weight Update (MWU) method
achieve optimal regret of O(y
in the presence of strong adversary Arora et al. (2012). With less information, the exponential-wette weight algorithm for exploration and exploitation (Exp3) achieves near-optimal regret O(
logn) given all historical information, T
n log n T
in the adversarial
bandit setup, where only the cost of one expert is observed on single day.
For large number of experts and days, it may not be feasible 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 al. (023) considers the experts problem in the data stream model. where the expert predictions are typically streamed through main memory, and 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 servers, and there is central coordinator who a low-regret
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Table 1: Summary of constant probability communication upper bounds.
UPPER BOUNDS
w/ A CONSTANT PROBABILITY
ALGORITHMS AGG FUNC
DEWA-S SUM
DEWA-M MAX
DEWA-L
DEWA-L
6p22
BROADCAST
Ó ( + O(Ts)
Ō + Ts)
Ō TT)
Ō RIनंTE + Ts)
MESSAGE-PASAEE
Table 2: Summary of our high probability communication upper bounds.
UPPER BOUNDS
w/ PROBABILITY 1 101-11/100 1/POLN(T)
ALGORIHTMS AGG FUNC
DEWA-S-P
DEWA-M-P
DEWA-L-P
DEWA-L-P
SUM
MAX
Ep>2
((++e<p52)
BROADCAST
Ó + T')
O +T))
O + Ts)
Ó Og + T's)
MESSAGE- PASSING
algorithm. However, communicating with different servers is expensive, and the goal is to design a low communication protocol that achieves low regret.
motivating example is a distributed online optimization problem, where different servers hold different samples, and each expert could correspond to different model in an optimization problem over the union of the samples as in the HPO-B real-world benchmark (Arango et al. 202T). this case, it is natural for the cost of an expert to be the sum of the costs of the expert across all servers. The goal thus to minimize the cumulative costs in an online fashion by choosing models on a daily basis. Another example of an aggregation function could be the maximum across servers; indeed, this could be useful there a maximum tolerable cost on the servers, which we would like not to exceed. For our lower bounds, expert it chose on a given day is non-zero; this is a minimal requirement of all cxisting algorithms, such MWU Exp3, which update their data structure based on such cost. It is also desirable in applications such as the experts problem where one wants to know the prediction was right or wrong.
also ask the protocol to be able to tell at least if the cost of the
In our setting, a coordinator needs to choose an expert based on historical interactions with s servers each day. We focus on two widely studied communication models, namely, the mexsage-passing model with two-way communication channels and the broadcast model with broadeast channel. In the message-passinngg model, the coordinator initiates 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 theory. can be viewed as a model for single-hop wireless networks. the broadcast model, each message exchanged is seen by all servers and the coordinator. We note that the broadcast model was a central communication model studied for clustering in [Chnn et al. (2016).
As in the distributed online learning setup, we can view each server database, where it possibly receives new data daily. The costs of the 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 implicit functions of the data, and if the latter, they may only need to be computed as required by the protocol.
We aim to achieve a near-optimal regret versus communication tradeoff in this setting over a horizon of days. Given the memory- streaming algorithms Srinivas et al. (2022); Peng & Zhang protocols.
(2022) and the close connection between streaming algorithms and communication-effonn one might think that implementing streaming algorithm in our settings optimal. While we could run streaming algorithm, critical difference here is that the coordinator is not -buuded 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 distributed Exp3 algorithm, which samples a single expert and thus has low communication, but maintains a weight locally for n experts using 2(n) memory. We stress this is not possible in the streaming model.

---

Table 3: Summary of our communication lower bounds. We assume R E (Oly Jog O
n log )]-
All lower bounds hold against oblivious adversarial cost streams with memory bound A O STR + 1) on the servers.
LOWER BOUNDS W/ CONSTANT PROBABILITY
AGG FUNC
BROADCAST
O ie - Ts)
CEESSAGE-PASSINE
With servers in the message-passing model and with sum aggregation, straightforward implemen-
tation of EWA achieves optimal regret O(v Ing with trivial communication cost of O s).
distributed Exp3 algorithm achieves O(V log regret with a total communication cost of (T'ss,
Here Ö(f) denotes f log 012) (nT's). A natural question is whether these bounds are tight and what the optimal regret versus communication tradeoff is.
We summarize our results in Table 1 Table and Table We assume R moloog I+f for DEWA-L as well as DEWA-L-P when 1 + < S 2, and
[Ö((
log T
F+f ((("loo
} for the others. All upper bounds hold unconditionally against strong adversarial cost streams. 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 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 more powerful machine than the individual servers. Empirically, we also provide comprehensive evaluations over real world (HPO-B Arango et al. (2021) as well as synthetic data traces to demonstrate the effectiveness of our methods.
RE (Ö logm) OV log
2 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 (195T): Robiison (195T). The exact form of MWU is carried out by adding randomness,
which efficiently solves two-player zero-sum games (Grigoriadis & Khachiyan 1995). Ordentlich &
Cover (9988 further proves the optimality of such algorithms under various scenarios. The algorithm
has later been adopted in wide range of applications (Cesa-Bianchi Bianchi & Lugosi, 2006 Freund &
Schapire 1997, Christiano et al. 2011 Garber & Hazan, 2016; Klivans & Meka 2017 Hopkins
al. 2020 Ahmadian al. 2022 including the experts problem. See the comprehensive survey
MWL 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 TTompson 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
ct al. 2013 Degenne & Perchet 2016 Agrawal & Goyal, 2017]] Kaufmannn 2018 Lattimore &
Szepesvári 2020 Auer et al.] 2002 Auer (002). As we mainly consider adversarial cost streams, the Exponential-welpe algorithm for Exploration and Exploitation (Exp3) and its Upper Confidence
Bound (UCB) variant most relevant due to their effectiveness in achieving near-optimal regret in the presence of adversaries (Auer et al. 2002).
Distributed learning with expert advice. Kanade et al. 2012 also study the expert problem under coordinator-servel model. However, the results are incomparable as Kanade al. 2212 considers the special case where the cost is allocated to one server rather than arbitrary number of servers,

---

which makes their setup special case under our more general scheme. Also, our lower-bound proof against oblivious adversaries rather than adaptive adversaries, as in Kanade et al. (2012). which is more challenging to prove. Detailed comparisons with Kanade et al. (2012) are described
in Section C
Hillel et al. 2013 Szorenyi et al. 2013 give a distributed MAB setting where arms on each server share the same cost distribution, and the goal is find the best arm cooperatively. Shahrampour ct al. 2017 Landgren et al. 2016; Bistritz & Leshem 2018 on the other hand, assume the costs on each server are i.i.d. across days while being different for different servers. Cesa-Bianchi et al. 2016 considers setup where servers are nodes on connected graph and can only talk to neighboring nodes while restricting the cost for each arm on the servers be the same within one day. [Krda et al.. 2016]studic the multi-agent linear bandit problem in a peer-to-pect to-eerr 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 outside of our scope (Anandkumar et al., [011] Besson Kaufmann] 2018 Bubeck et al. 2020 Wang et al. 2020). Unlike most of these setups, we make no assumptions about the costs across days and servers.
Distributed fuucctionl monitoring. The coordinator-serve communication model is also commonly seen in the distributed functional monitoring literature (Cormode et al. 2011] Woodruff' & Zhang 2012 Arackaparambil et al., 2009; Cormode al.) 2012 Chan et al., 2012). where the goal is to approximate function values, e.g., frequency moments, across streams with minimal communication. 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.
3 Preliminaries and Notation
We use T to denote the total number of days, the number of experts, and the number of servers. ii represents the cost observed at step for expert i on the j-th server. I denotes an estimate to ( and [x] denotes {1, 2, .,.....,.,, ,... A word of memory represented as Ollog (nTT) bits and we use Ó()) to suppress log 0(1) s)) factors. We refer to the Exponential Weight Algorithm (EWA) and Multiplicative Weights Update (MWU) method interchangeably.
3.1 Distributed Experts Problem
In the single server expert problem, each expert e;, i E [m]] has its cost 15 E [0, on day L. Based on the history, algorithm A needs select one expert (Aii) 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) = Eا= l'xce - minn- Et= (
In the distributed setting, we have 8 servers and one coordinator where the cost & now depends on costs (5, observed locally across all the servers. The coordinator selects the expert for the next day based on any algorithm A of its choice. For each E [s], the j-th server can receive or compute its cost ( E [n]] for the i-th expert on day t. The actual cost for the i-th expert on day is defined as 1 = "4,, ..,.). where f(() is an aggregation function. We assume the costs 1i are non-negative. We consider three natural choices of f(): 1. the summation function 1, = Σド Pi Σド )
(1,)) 2. the maximum/nininum function 2 max [1, 3. the fpx1 norm function, 1 (Ei-1 ((.)) .P .P> In the distributed setting, regret is defined as in the single server setup with 25 = [(] Pi.2: ... ..,...))) Without loss of generality, we normalize I E [o, 17, ; 2 0. In practice, i E [0. pl. the regret will increase by a factor of p accordingly, which only affects the scale of the regret and preserves optimality. 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:
and integer power of the sum function
Message-passing model. For the peessage-passing model, the coordinator can initiate two-way private channel with 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). We leave the definition and description of strong adaptive adversaries and the EWA algorithm Definition A.1 and Appendix A.2 accordingly.
4 Proposed Algorithms
4.1
Overview
In the message-passing model, we let be E [ri] be a hyper-parameter of our choice. We first propose a baseline algorithm DEWA-S that can achieve Ö(
12
regret with constant probability using
Tb.
O + s)) total communication when the aggregation function is the summation function or an integer power of sum function. The intuition for the baseline algorithm is to get an unbiased estimation of the experts' underlying cost by sending signal to the coordinator with probability that proportional to the local cost, which is simple yet effective. We further introduce the full
algorithm DEWA-S-P that achieves Öly Tb. regret with probability 1 poa(2ry using Ö + +))
total communication. Both DEWA-S and DEWA-S-P work in the broadcast model with the same guarantees since the mhessage-passing model only more costly.
In the broadcast model, we propose DEWA-M-P that achieves Ō(
12 Tb,
regret with probability
1 1 and using only Ö(T(be + s)) overall communication when the aggregation function is the maximum function. Besides the summation aggregation function, we leverage a random-we walk-based communication protocol to find out the aggregated cost with a minimal communication cost. 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 each day by querying each of the servers for that expert's
(Tly(T)
cost on that day. Lastly, we propose DEWA-L-P that achieves O(( log ) + V Tog regret with
Tb. )
probability poly(T) and using only ÖT + s)) overall communication when the aggregation function is the -p-norm function for any fixed constant 0 < S such that 1 1+ < p. The algorithm employs the idea of embedding lp into Lo. thus efficiently estimating the aggregated cost using the previously introduced DEWA-M-P... For all our bounds, be E [r]] is hyperparameter that trades off the communication with the optimal regret can get. For instance, setting d. o(1) can
achieve regret of R R= Ö
T no and setting b o(n) can achieve a regret of R= =6(V 1ogn).
Thus, setting b. ol TR2 can achieve the optimal communication bound we provide in Table 1
and 2
4.2 DEWA-S
We describe DEWA-S in Algorithm The intuition is to obtain an unbiased estimate i for 1e using limited communication and then run EWA based on our estimate. More precisely, we use the following estimator to estimate 1 on day Iς b. (Ej=aa random variables following af -Berooull(( (44 and the Bi, are sampled from Bernouli((( As [0, 11, Hi, 0. Bernoulli( (1, is valid distribution. We can easily verify that this is an unbiased estimator: EE( E ((, = Fo, I(L = -.- Σラ= bul = 15 The same sampling technique can be used to obtain an unbiased estimator of 1Ç when the aggregation function is an integer power of the sum over local costs, where each monomial in the expansion the aggregation function is unbiasedly estimated by taking the product of sampled local costs. On each communication cost is O + s)).
where of are i.i.d. Bernoulli
day, only incur communication cost O(s Ei du E'=1' (ig)) O + s). Thus, the overall
5

---

Algorithm 1 DEWA-S
Input: learning rate 7, sampling budget be:
Initialize L5 0, Vi E [xd]
for (= to T
Coordinator chooses expert with probability p(i) x exp (-n14- for j = 1 to s do
Coordinator initiates private channel with server j; for i to do
Server j observes cost H and samples o ~ Bernoulli( ), |8,, ~ Berouuli(11,) )):
Server j sends tuples (i.j) to the coordinator if ai, 1, B and clears its memory;
Coordinator calculates i 2. (Ei= oi.)
Update L, by L L f-11_ + R. Vi E [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 The idea is to run multiple baseline algorithms in parallel to boost the success probability, where we regard each baseline algorithm as meta-expert. As each meta-expert has constant success probability, the probability that they all fail is exponentially small in the number of eeta-experts. Thus, by running EWA on the meta-experts, we can follow the advice of the best meta-expert and achieve near-optingg near-optimal regret with high probability.
Algorithm DEWA-S-P
Input: learning rate Ameta sampling budget be. failure rate 1/poly (T);
Let K llog (poly(T))),, initialize K baseline algorithms A. and let Li = 0, [K]; for = to T do
Coordinator chooses expert according to (x with probability p(k) exp (- (-Thmets T.(
Coordinator updates memory states for all As according Algorithm
Coordinator receives cost (aAatt Σj=1 (A.
Update all La by LA LA + (A2()))
More precisely, to obtain poly[T] success probability, we initiate [log (poly(T)) meta-experts Ag, k E [ílog (poly(T))]] at the start of the algorithm. Each meta-expert runs its own DEWA-S independently across days. The cost the k-th meta-expert on day t is defined to be the cost the expert Aş selects on the same day, which is denoted l (a))))) With the definition of the cost for the meta-experts,
then run EWA on the meta-experts.
The meta-level EWA needs to know the actual cost (A from the s servers of each meta-expert in order to recover the best meta-expert with 1 poly(T) success probability. Therefore for DEWA-S-P, on each day, incur communication cost of Ö(s + (b. + s) log (poly(T))) Ô(b + s), and the overall communication is Ö(T(b. +)).
4.4 DEWA-M-P
We propose DEWA-M described in Algorithm 3 that achieves ncar-optimal regret versus communi- cation tradcoff up to log factors for the maximum aggregation function in the broadcast model.
The intuition of DEWA-M is that for each expert, if we walk through the servers random order and only update i we encounter Hi, > 75, then with high probability, we only need small number of updates per expert. This cannot be achieved in the cessage-passingg model due to the fact that broadcasting i requires ((s) communication per expert. In contrast, communication is required for broadcasting i in the broadcast model. In fact, with probability 1-6 8, each expert will update most (llg(ss/5) times. By setting
poly and applying union bound over sampling budget b. and number 7 of days, we have the desired low communication with probability at least 1 poly(T)- More precisely, we have the following theorem (see detailed proof in Section B.1

---

Algorithm 3 DEWA-M
Input:
learning rate y, sampling budget be:
Coordinator initializes L, Vi [n]:
for to T
Coordinator chooses expert with probability p(i) & exp --1,--1 Coordinator randomly chooses be experts with corresponding IDs B. [t(1), :(bb)):: Coordinator initializes ? = 0, Vi E [rd]
Coordinator permutes [s] randomly and denotes the resulting sequence as St
for j in St do
Coordinator initiates channel with server j;
for ř 1 to x do
Server j observes cost y and sends (J to the coordinator if (4, > 1t and Be: Server j cleans memory buffer;
Coordinator updates with received y
Update 7. by f. = f 7/-1 + Ri, vi [n];
Theorem 4.1. For a sampling budget be E [m]) with probability for DEWA-M is Ô(T(he + 8)).
poly(T)) the communication cost
Even though we have a high probability guarantee with minimal communication, we still only have constant probability guarantee for achieving optimal regret O(v log")) ). We can boost the success b,
probability using the same trick as in Algorithm 2 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 Section
Theorem 4.2. For sampling budget be E [m], with probability 1 for DEWA-M-P is ( + 8)).
poly(Ty the communication cost
4.5 DEWA-L-P
In this section, we present DEWA-L (Algorithm 4 for the fp>1 norm aggregation function in the broadcast model. The key idea of DEWA-L is embed fp into foo using the min-stable property of exponential distribution. More specifically, F, standard exponential random variable, then
(1
(C) y
max E
E
where also standard exponential random variable. Therefore, we can
employ DEWA-M efficiently compute (t)) and obtain an unbiased estimator of & by normalizing.
Algorithm 4 DEWA-L
Input: learning rate 7, sampling budget b.: Coordinator initializes L. vi [n]:
for to T
Coordinator chooses expert with prohability p(t) x exp (-1i 1 Coordinator randomly chooses be experts with corresponding IDs B. (t(1), -. ((bb)))
Coordinator initializes i = 0, vi E [n]]
Coordinator permutes [s] randomly and denotes the resulting sequence as St
for j in S. do
Coordinator initiates channel with server j; Server j samples F.y ~ Exponential(1): for ? to n do
Server j observes cost (i,, and computes cf., = )1
E,
Server j sends cf,, the coordinator if ct,; ct and i Be;
Server j cleans memory buffer;
Coordinator updates of = max; ci,, with received c(.j;
(c))²/>
Coordinator computes i,
1-(1 -e 1/o]> where E Exponential(1):
Update L. by i f + Vi [n]:

---

It is not hard to see that the communication cost of DEWA-L stays the same as DEWA-M. In terms of regret, if we fix any constant S such that 1 1+2 E < p. DEWA-L achieves vanishing regret R = ( logo Tbe ) with constant probability. Note that, for fy-norm functions with p 2, by choosing 1, we obtain a near-optimal regret versus communication tradeoff up to a log factor
log
R
O Tbe
Again, get the high probability regret guarantee of DEWA-L, we propose
DEWA-L-P that initiates log (poly(T)) copies of DEWA-L as meta-experts and runs EWA top of them. More precisely, we have the following theorem with the same proof as Theorem
Theorem 4.3. For a sampling budget be E [ra], with probability poly(TT' the communication cost for DEWA-L-P ( +)).
5 Formal Guarantees
We present formal regret analyses of DEWA-S, DEWA-S-P, DEWA-M-P and DEWA-L-P. We show that DEWA-S can achieve regret Rt = =0
logn
with probability at least 9/10, DEWA-S-P and
Tb.
DEWA-M-P achieve regret R =O(v
n log (nT)
with probability at least 1 poly(7)) and lastly
The
DEWA-L-P can achieve regret R O(( l.lng ) +
T
with probability least 1 Poly(T)
Tb.
for any fixed constant 0 < E S such that t+
We then give 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. holds for oblivious adversarial cost streams, and thus also for strong adversarial cost streams and the message- paasaggg model. We use the communication lower bound for the e-DIFFDIST problem Srini- vas al. (2022) but adapt experts problem, we prove that any protocol for achieving A regret with constant probability requires total communication at least ??( R2 ). It will follow that DEWA-S, DEWA-M and DEWA-L (p 2)
setting. By reducing the e- E-DIFFDIST problem to the distributed
are optr-optimal in their communication for all regret values E [0(
log
Oly
Alogm )
T
5.1 Upper Bound
We state our regret upper bounds for DEWA-S in Theorem
DEWA-S-PP in Theorem 5.2 DEWA- M-P in Theorem 5.3 and DEWA-L-P in Theorem 5.4 The detailed corresponding proofs can be found in Section B
5.1
Theorem 5.1. For be E [n], DEWA-S achieves regret R O(y (nlogn) ((1 with probability at least TO
The
for the distributed experts problem in the message passing model with the summation aggregation function and for strong adaptive adversarial cost streams.
Theorem 5.2. DEWA-S-P achieves regret R R= O log (nT)
with probability at least 1
The
poly(T)
for the distributed experts problem in the message passing model with the summation aggregation function and for strong adaptive adversarial cost streams.
Notice that the total communication cost for DEWA-S-P Ô + +))) Thus DEWA-S-P can achieve the same regret as EWA with high probability guarantee when b n, but requires only ÖT + s)) communication instead of (nniss communication. DEWA-S-P further generalizes to the case when be < n.
with probability at least Poly(T) for the distributed experts problem in the broadcast model with maximum aggregation function and for strong adaptive adversarial cost streams.
Theorem 5.3. DEWA-M-P achieves regret R = O(v
log (n'T'
The
Theorem 5.4. Fix any constant < < 1 such that 1 + <. DEWA-L-P achieves regret
1 1 + TogT with probability at least - pois(T) for the distributed experts problem the broadcast model with Ep norm aggregation function and for strong adaptive adversarial cost streams.
R = O((" log
The
8

---

Table 4: Communication costs the real-world HPO-B benchmark in different settings. We use EWA as the comparison baseline. E.g., DEWA-S only costs about 0.07 communication of EWA.
ALGRITHTM
EWA SUM MAX
EXP3 SUM / MAX
DEWA-S SUM
DEWA-M MAX 1/n
AGG FUNC
SAMPLING BATCH be
1/n
BLACKBOARD
0.0849x 0.1834x
1x
0.1453x
0.0730x 00.075xx
PEASAGE-PAASSNN
Since the regret and communication bounds hold with probability least union bound, they both hold with probability at least 1 poly(T))
individually, by
poly(T)
5.2 Lower Bound
Theorem 5.5. Let < 1 be fixed constant that is independent of the other input parameters, and suppose M ( SI + 1) is an upper bound on the total memory server can store from previous days. Any algorithm A that solves the distributed experts problem in the broadcast model with the 6p(1 S p (6) norm aggregation function with regret R and with probability least 1 pp needs at least 22( T22 bits of communication, If the al algorithm can also determine, with probability at least 1 1-p. the cost of the selected expert on each day is non-zero, then it also needs ((T'ss bits of communication. These lower bounds hold even for oblivious adversarial cost streams.
We present the proof of Theorem 5.5 Section B.7
Additionally, we present an Miss) communi- cation lower bound proof below for achieving sub-constany regret with the maximum aggregation function in the bessaae--assiing model, which optimal for T E Oppoly ployyylog (ns))). This indicates that we cannot do better than naīve EWA in this case, which achieves optimal regret with communi-
cation Ö(s)). Note that within the optimal regret R [O(v
log T
Oly
loz )]
in which we are
interested, the T term can be canceled out by the term in R². So, the memory bound assumption does not depend on the time step T.
Experiments
In this section, 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 black-box hyperparameter optimization benchmark, we can regard different models the HPO-B benchmark as different experts in the distributed experts problem, and different datasets 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 datasets for a search step. Thus, minimizing regret directly corresponds to optimizing the overall accuracy across all search steps. For both DEWA-S and DEWA-M, we set 1 to compare against Exp3 and be to compare against EWA.
The results in Figure D Figure 2 and Table 4 show that algorithms achieve similar regret as the optimal algorithms (Exp3 and EWA) while having less communication cost. We further use two synthetic datasets evaluate and sparse-cost. We present the results in Section D which show that our algorithms can achieve near-optimal regret with significantly lower communication cost across all scenarios consistently.
algorithms under various scenarios, including dense-cost
Acknowledgements
David P. Woodruff was supported in part by Simons Investigator Award and NSF CCF-2335412.

---

DEMA
DERA
62
Regiet
Rogiet
Regiet
Regint
(a) Regret
(b) Regret be
(a) Regret be
(b) Regret n2.
Figure 1: Regrets on HPO-B w/ sum aggregation. Figure 2: Regrets on HPO-B w/ max aggregation.
References
Aamand, A., Chen, Y., Nguyen, H. L., and Silwal, S. Improved space bounds for learning with experts. arXiv preprint 23t.::2303.01553,, 2023.
Agrawal, S. and Goyal, Near-optimal regret bounds for thompson sampling. Journal of the ACM (JACM), 64(5):1-24, 2017.
Ahmadian, S., Esfandiari, H., Mirrokni, V., and Peng. B. Robust load balancing with machine learned advice. In Proceedings of the 2022 Annual ACM-SIAM Symposium Discrete Algorithuss (SODA), pp. 20-34. SIAM, 2022.
Anandkumar, A., Michael, N., Tang, A. K., and Swami, A. Distributed algorithms for learning and cognitive medium access with logarithmic regret. IEEE Journal on Selected Areas Communica- lions, 29(4)7731-745, 2011.
Arackaparambil, C., Brody, J., and Chakrabarti, A. Functional monitoring without monotonicity. In Automaia, Languages and Progrumming: 36th International Colloquium, ICALP 2009, Rhodes, Greece, July 5-12, 2009, Proceedings, Part 36, pp. 95-106. Springer, 2009.
Arango, S. P., Jomaa, H. S., Wistuba, M., and Grabocka, J. Hpo-b: A large-scale reproducible benchmark for black-box hpo based on openml. arXiv preprint arXiv:2106.00 06257, 2021.
Arora, S., Hazan, E., and Kale, S. The multiplicative weights update method: meta- meta-algorithm and applications. Theory of computing. 8(1):121-164 2012.
Audibert, J.-Y., Bubeck, S., et al. Minimax policies for adversarial and stochastic bandits. In COLT, volume 7, pp. 1-122, 2009.
Auer, P. Using confidence bounds for exploitationneexplrraion trade-offs. Journal of Machine Learning Research, 3222,).397-422, 2002.
Auer, P., Cesa-Biancha N., Freund, Y., and Schapire, R. E. The nonstochastic multiarmed bandit problem. SIAM journal computing, 32(1):48-77 77, 2002.
Besson, L. and Kaufmann, Multi-player bandits revisited. In Algorithmic Learning Theory, pp- 56 56-92. PMLR, 2018.
Bistritz, and Leshem, A. Distributed multi-player bandits a game of thrones approach. In Bengio, S., Wallach, H. Larochelle, H., Grauman, K., Cesa-Bianchi, N., and Gar- nett, R. (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. URL https: https://procedings.eeet www.innuriii.. http./aaap.ppccppprp////0...... (2260cac002226222622222222 Paper pdf
Braverman, M., Ellen, F., Oshman, R., Pitassi, T., and Vaikuntanathan, V. A tight bound for set disjointness in the cressage-passingg model. 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pp. 668-677 IEEE, 2013.
Brown, G. W. Iterative solution of games by fictitious play. Act. Anal. Prod Allocation, 13(1):374, 1951.
10

---

Brown, G. W. and Von Neumann, J. Solutions of games by differential equations. Technical report, RAND CORP SANTA MONICA CA, 1950.
Bubeck, S., Li, Y., Peres, Y., and Sellke, M. Non-stochastic multi-player multi-armed bandits: Optimal rate with collision information, sublinear without. In Conference Learning Theory, pp. 961-987. PMLR, 2020.
Cesa-Bianchi, N. and Lugosi, G. Prediction, learning, and games. Cambridge university press, 2006.
Cesa-Bianchi, N., Gentile, C., Mansour, Y., and Minora, A. Delay and cooperation in nonstochastic bandits. In Conference Learning Theory, pp. 605-622. PMLR, 2016.
Chan, T. H. H., Li, M., Shi, E., and Xu, W. Differentially private continual monitoring of heavy hitters from distributed streams. In Privacy Enhancing Technologies: 12th International Symposium, PETS 2012, Vigo, Spain, July 1 11-13, 2012. Proceedings 12, pp. 140-159. Springer, 2012.
Chen, J., Sun, H., Woodruff, D., and Zhang, Q. Communication optimal distributed clustering. Advances in Neurul Information Processing Systems, 29, 2016.
Christiano, P., Kelner, J. A., Madry, A., Spielman, D. A., and Teng, S.-H. Electrical flows, laplacian systems, and faster approximation of maximum flow undirected graphs. In Proceedings of the forty-third annual ACM symposium Theory of computing, pp. 273-282, 2011.
Cormode, G., Muthukrishnan, S., and Yi, K. Algorithms for distributed functional monitoring. ACM Transactions on Algorithms (TALG), 7(2):1-20, 2011.
Cormode, G., Muthukrishnan, S., Yi, K., and Zhang, Q. Continuous sampling from distributed streams. Journal of the ACM (JACM), 59(2):1-25, 2012.
Degenne, and Perchet, V. Anytime optimal algorithms in stochastic multi-armes bandits. In International Conference on Machine Learning. pp. 1587-1595, PMLR, 2016.
Dixon, M. F., Halperin, I., and Bilokon, P. Machine learning in Finance, volume 1406. Springer, 2020.
Doyle, J. C., Francis, B. A., and Tannenbaum, A. R. Feedback control theory. Courier Corporation, 2013.
Freund, Y. and Schapire, R. E. A decision-theorets generalization of on-line learning and an application to boosting. Journal of computer and system sciences, 55(1):1 15(1):199133, 19-1139, 1997.
Garber, D. and Hazan, E. Sublinear time algorithms for approximate semidefinite programming. Mathematical P Programming, 158(1)33293361, 2016.
Garivier, and Cappé, The kl-ucb algorithm for bounded stochastic bandits and beyond. In Proceedings of the 24th annual conference on learning theory, pp. 359-377-7777 JMLR Workshop and Conference Proceedings, 2011.
Grigoriadis, M. and Khachiyan, L.. G. A sublinear-time randomized approximation algorithm for matrix games. Operations Research Letters, 18(2):53-58, 1995.
Hazan, E. et al. Introduction to online convex optimization. Foundations and Trends@ in Optimization, 2(3-4):157-325, 2016.
Hillel, E., Karnin, Z. S., Koren, T., Lempel, R., and Somekh, O. Distributed exploration in multi- armed bandits. Advances in Neural Information Processing Systems, 26, 2013.
Hopkins, S., Li, J., and Zhang, F. Robust and heavy-tailed mean estimation made simple, via regret
minimization. Advances in Neural Information Processing Systems, 33:1 1902-11912, 2020.
Kanade, V., Liu, Z., and Radunovic, B. Distributed non-stochastic experts. Advances in Neural Information Processing Systems, 25, 2012.
Kaufmann, F. On bayesian index policies for sequential resource allocation. The Annals of Statistics, 46(2):842-863 2018

---

Klivans, A. and Meka, R. Learning graphical models using multiplicative weights. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp. 343-354. IEEE, 2017.
Korda, N., Kaufmann, E., and Munos, R. Thompson sampling for I-dimensional exponential family bandits. Advances in neural information processing systems, 26, 2013.
Korda, N., Szorenyi, B., and Li, S. Distributed clustering of linear bandits in peer to peer networks. In International conference on machine learning, pp. 1301-1309. PMLR, 2016.
Landgren, P., Srivastava, V., and Leonard, N. E. Distributed cooperative decision-making in multi- armed bandits: Frequentist and bayesian algorithms. In 2016 IEEE 55th Conference on Decision and Control (CDC), pp. 167-172. IEEE, 2016.
Lattimore, T. and Szepesvári, C. Bandit algorithms. Cambridge University Press, 2020.
Ordentlich, E. and Cover, T. M. The cost of achieving the best portfolio in hindsight. Mathematics of Operations Research, 2344)9960-982, 1998.
Peng. B. and Rubinstein, A. Near optimal memory-regret tradeoff for online learning. arXiv preprint arXiv:2303.01673, 2023.
Peng, B. and Zhang, F. Online prediction in sub-linear space. arXiv preprint arXiv:2207.07974, 2022.
Robbins, H. Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Sociery. 58(5):527-535, 1952.
Robinson, An iterative method solving game. Annals of mathematics, pp. 296-301, 1951.
Shahrampour, S., Rakhlin, A., and Jadbabaie, A. Multi-armed bandits in multi-agent networks. In 2017 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 2786-2790 IEEE, 2017.
Shalev-Shwartz, S. et al. Online learning and online convex optimization. Foundations and Trends in Machine Learning, 4(2):107-194, 2012.
Srinivas, V., Woodruff, D. P., Xu, Z., and Zhou, S. Memory bounds for the experts problem. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, pp. 11 1158-1171, New York, NY, USA, 2022. Association for Computing Machinery. ISBN 9781450392648. doi: 10.1 10.1145/35199335.522222 3520069
httpss//:////o org/ 10. 1145/3519935
Szorenyi, B., Busa-Fekete, R., Hegedus, I., Ormándi, R., Jelasity, M., and Kégl, B. Gossip-based distributed stochastic bandit algorithms. In International Conference Machine Learning, pp. 19-27. PMLR, 2013.
Thompson, W. R. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3-4):285-294, 1933.
Wang. P.-A., Proutiere, A., Ariu, K., Jedra, Y., and Russo, A. Optimal algorithms for multiplayer multi-armes bandits. In International Conference on Artificial Intelligence and Statistics, pp. 4120 4129. PMLR, 2020.
Welzl, E. Basic examples probabilistic analysis, part reading assignment for predoc course on randomized algorithms. 01 2000.
Woodruff, D. P. and Zhang. Q. Tight bounds for distributed functional monitoring. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pp. 941-960, 2012.
Woodruff, D. P., Zhang, F., and Zhou, S. Streaming algorithms for learning with experts: Deterministic versus robust. arXiv preprint arXiv:2303.01709 2023.
12

---

A Preliminaries
A.1 Strong Adaptive Adversaries
Definition A.I. (Distributed experts problem with strong adversary). An algorithm A run by the coordinator makes predictions for T days. On day t:
1. A commits distribution ps experts based on the memory contents of the coordi- nator on day 1.
2. The adversary selects the cost f each server after observing Pt-
3. A selects an expert according to Pt 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 (i,s with no knowledge of the internal randomness or state of A, as oblivious adversaries. Notice that we send each of the server's local information to the coordinator each day, then running the Exponential Weight Algorithm the coordinator gives
optimal O Jogn regret for strong adversarial streams. However, the communication cost is prohibitive (n!''s words.
A.2 Exponential Weights Algorithm
As we will use the Exponential Weights Algorithm (EWA) as sub-routine, we briefly describe it in Algorithm
We have the following regret bound for EWA:
Algorithm 5 Exponential Weight Algorithm (EWA)
Input:
lcarning rate Initialize Z, 0, Vi E [n]: fort= to T do Sample expert with probability p(i) x exp (-11 --y1
Update L2 by L L 11, Vi (n);
Lemma A.2. (EWA regret, Arora et al. (012))) Suppose n, T, 11 > 0, t [T), and ( E [0, 1 Let Pt
be the distribution committed by EWA on day t. Then: ( (pr. 12) min,- [[m] Σ 1 S
log TT
+ 17. And with probability at least 5, the average regret is bounded by: R(A) S log log (aT) T
T
log a and ō poty(T) gives us O(y + Oly log (n/(6) Thus, taking = /
regret with
probability at least [T]
B Proofs.
B.1 Theorem
In order to prove the communication bounds, we need the following lemma:
Lemma B.I. Welzl 2000)). With randomly permuted sequence S = {ai, 02, , an and 7 0, we read from left right and update 7 a; whenever encounter as > 7, define random variable X as the number of times has is updated during the process. We have the following results:
E [2x] =n+1
Given Lemma B.I we can then prove our statement.
Proof. For any expert on any day, we will first prove that with probability at least 8, the servers only need to send the corresponding cost to the coordinator at most O(log (s/6) times. By
13

---

Lemma
B.1
with n = s in our setup, for any 9 2 0, we have:
Pr(X > g) (2x > 29)
1*x
29
8 +
29
By setting g = log (* we have Pr (X < log ( (*$1)) ) > 1 8. Furthermore, letting 8 bypoly(7))
we have
Pr(X log ((s + 1)b.poly(T)) (T)))
(opoly(T)
By a union bound over the be sampled experts and T days, the above guarantee simultaneously holds for all experts sampled and all days, with probability at least 1/poly(T). The overall communication is then:
$
X
i=1
be
$
log ((s +))b.poly(T))
j=1
=Ts The log ((s 1)bapoly(T))
=Ō(T(b. +8))
which completes the proof.
In addition, in cases where the coordinator does not need to initiate communication, we can achieve an Obb, log (s/8) communication cost per time step with the following protocol: Initialization: each individual server initializes a h to record the maximum cost for each expert. 1. For each server who has cost larger than the current maximum, send its value to the broadcast channel after 6,,; time delay, where وūg is randomly sampled from [0, 1]. 2. Once the broadcast channel has been occupied, all other servers stop the sending action and update their corresponding fi; 8.,, instead. Then we can repeat this process and use the maximum value collected after unit time steps as an estimate to the maximum value. In this protocol, we assume that the broadcast channel can only be occupied by server. The random ordering is guaranteed by the random delay and the expected number of communication rounds to get the maximum value is given in Lemma B. Additionally, notice that for each time step the protocol is guaranteed to end within time steps as the worst delay unit time step for each server. By using this protocol, we can still obtain a near optimal communication cost of Obb log s/5).
B.2 Theorem
Proof. Let C be the communication required to obtain the cost of one expert on a single day. From proof of Theorem 4.1 we have C = O(log ((s + l)b.poly(7))) with probability
b. For DEWA-M-P we need this communication bound hold for Tb, log (poly(T)) + T log (poly experts and meta-experts simultaneously across horizon of T days. By union bound, the failure rate is
The log (poly(T)) Tlog (poly(T)) 1/poly(T).
bepoly(TT)
As the communication cost of each expert and meta-expert is
O(log ((s + 1)b.poly(T))) = =(1
the overall communication cost is thus
Õ + Tb. log (poly(T')) + T log (poly(T))) = Ö(T(be +
with probability at least 1/poly(T),, which concludes the proof.
14

---

B.3 Theorem 5.1
We need the following lemmas:
Lemma B.2. Define i - Ei 41 of
Ev exp (-nbiy Define w; = 10
expl (-pl
T ,4
(i.... TT and is of our choice. For all 1 2 E O. we have the following result:
T
T
log n
Σ ( (t)
min 1 I
c (
Proof. Define 4, log Ei= exp (-ní!)
We have:
DT 20
1t-1
(npit-1) exp (-ni?)
T
Li=1 exp
log
Σ exp
(-nii-)
n
(-nit)
log
mi exp
77
E + 1) n 1+e (2) 1)
log
1- n1 +
stft
1+s w/ (1))
17
E + 1)
1=1
Σ
1f
( 1)
where we used Vz 2 0 1 x for the second inequality.
s(=+1) x for the first inequality and Vz, log (1 + z)
As Do log by definition, have: 7
T 4 +
logn n
n
>
Σ (e)
(E + 1)
1=1
T
(1)r,1))
min LT
where the second inequality holds due the fact that Vi E [n]:
TT log
Σ 1=1
exp
(-nit)
7
2 log eepp (-nii:)
1
> - L
15

---

Lemma B.3, Let R be the average regret over T days. Then,
T (e)
1
E[R]
E
(20e
min D
T
Proof. We have:
T-B B[R
E
(1rr, 4e)
min L,"
IE
(wer (e)
min LT=
IE
Keies (e)
min E L
(1ie, 1e)
min LTT
E
(10e, (e) min LT
Line 3 is due to l, being independent of dà on day t and & is unbiased estimator. Line 4 is by Jensen's inequality.
Proof. Back our proof for Theorem 5.]
we have:
T
T
R
E
Σ
1e)
min LT
(by Lemma B.3
1=1
E
log 72
17
(0))
(by Lemma B.2 with 1)
11
2
t=1
log 71
11
E
ai (1))
T
log n
Σ
(
2
T
log n
2n
E
1)
b
t=1
log n
Tn
b
16

---

Line 5 is by:
E
bp
1=1
2
Σ
E
[
st +
Σ
62
F=1
n2
6
1
+
6
n2a
j=1
jzh
n
b
6
2n
62
n2a
be
j=1
Take 17 V
logn Tn
We then have:
log Tbe
E[R] S 2
Due to R >> 0, by Markov's 's inequality we have:
n log Tbe
E
1
Pr
R > 1
20
n Tb.
10
which concludes our proof.
B.4 Theorem 5.2
Proof. Let by E [n] and K [log (poly(T))]. Let A2,, .Ax ) be K independent DEWA-S exte-experts initiated with be, b.. Let Aa = S be the event that A, successfully achieves regret
log and let A₂ F be the event that it fails. From Theorem 5.1 we have: Oly Tb.
1
Pr(A: F)
10
Thus, the probability that the best meta-expert achieves regret Oly
logn Tb.
can be lower bounded by:
K ÚLAL= (odk=s)) =1 21 21 1 2 1 1/poly(T)
Pr
k=1
By Lemma
A.2
running EWA on top of these meta-experts gives regret:
ni log n
log (K/0),
R R= R=O(v
O(y
The
T
with probability 1 - 1/lpbll - 5 (by union bound). Letting 5 = 1/poly(T") then guarantees an regret with probability least 1
O(
log (nT)
2 po) which concludes the proof.
B.5
Theorem
5.3
Proof. For DEWA-M we have a constant probability guarantee to have regret R O(v n log (n)
The
The proof simply follows from the proof of Theorem 5.1 except that now have actual cost for the
17

---

sampled experts instead of unbiased estimates. More specifically, we have:
T
T
R
E
Σ
1))
min LT:
log n
<
E
71
2ot (2:)
T
log n
E
dtt (2))
1
t=1
log n
1
E
ve
((
"
log n1
T
n2 by
1
E
log
T'm
1)
1
be
Take 17 V
b. log Tn
We then have:
log
E R
S 2
Tbe
Since R > 0, by Markov's 's inequality we have:
n log
E[
1
Pr
R
201
The
10
20
Tb.
Thus, with probability at least DEWA-M has regret R = O log (xz)
Since we have initiated
Tbe
log (Poly(T)) independent instances of DEWA-M, we have probability at least 1 1 1/poly(T) that
of the instances of DEWA-M achieves regret R O(v on top of these meta-experts gives us regret:
"
11 log (u] By Lemma A.2 running EWA
Tb.
|n
log (log (poly(T))/O) (T))/8)
R ==00 =ly
+ +v6
Tb.
T
with probability - 1/poly(T) - 8 (by union bound). Let 8 1/poly(TT). This guarantees an poly(T)) which concludes the proof.
(
Ing (xTT)
regret with probability at least 1
2
Tb.
18

---

with probability at B.6 Theorem 5.4
Proof. We first upper bound the expected average regret of DEWA-L Since p > for any fixed
constant e > 0 such that + E < p. by Lemma B.2 and Lemma B.3 we have:
T E
R
E
(ws, b2) min LT-
17 log
E
E (E + 1)
T
log 7
rf
Σ
( + 1)
t=
log n
rff
E
i
1
"
(E +1)
1=1
log
rff
Σ
( 1)
by
log n
O o
((
m
bn
Let 1 - (1 (1-1) 2)
be
be the probability that an expert gets picked into B.. Line 4 is by:
[+s
E
(ct)
(+=)/=
= q
ql
Elte
E-1/p
E
(1S)
ltc E (1+6)//
q
E E-1/pp]
1+s E F. F1(++))
q-
(1))
E E 1/p]
E F (1++)/p
S q
(as S 1 S 1)
E F 1/p
0
(
(as E
E (1+6)/7
and E E 1/2 converge)
o
be
Pick 17 (bx) Ing
then have:
(nlogn 14c be
T- [R][ =0 0 T
Hence,
((
(nlogg Tb.
I+c
E R =0
(
By Markov's inequality. DEWA-L has average regret R O (nlogg
I+c
Tbe
least T0
Since we have initiated log (poly(T)) independent instances of DEWA-L, we have probability at least 1 1/poly(T') that one of the instances of DEWA-L achieves regret R
n log a The
14c
19

---

By Lemma A.2 running EWA on top of these meta-expent gives us regret:
R R= (( nllog n
(V
log (log (poly(T))/8)
+0
Tbe
with probability
- 1/poly(T) - 8 (by union bound). Let á = 1/poly(7). This guarantees an
O
14c
log T
regret with probability at least poly(T) which concludes the proof.
Tb.
B.7 Lower Bound Proof
The communication lower bound proof for the maximum aggregation function in the message-pasee peassng model follows using the multi-player number-in-hen in-hand communication lower bound for set disjointness in Braverman al. (2013). To solve the multi-player set disjointness problem with players, where each player has bits of information cf {0, 1), E [n].j [s], the communication lower bound is ((ns) for the message message-passing model.
In our problem, in the first case, all experts have at least one server that has cost of 1, i.c., Ej E [s], Vi E [m], = 1. In the second case, we have one expert whose cost every server is O 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 maximum cost of 0 while all other experts incur maximum cost of 1. If we can decide which case we are in, then we solve the set disjointness problem, and thus there an 2(nss) communication bound. By copying the same hard instance over T days, it follows that 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 pesssage-passing model. Note that EWA can achieve the optimal regret with ((n)) communication if we assume T E (poly (log (ns))), and therefore, we cannot do better than EWA up to logarithmic factors with the maximum aggregation function in the message-passing model. To give the lower bound proof, we first define the DIFIIIIT problem.
Definition B.4. (EDDIFFDIST problem. Srinivas et al. (2022) ). There are players, and each has n
bits of information indexed from 1 to n. Let μo = Bernoulli (1), An = Bernoulli(] 2 c), we must distinguish between the following two cases:
(Case A). Each index for each player is drawn i.i.d. from 140-
(Case B), An index E [m] is randomly chosen, then the i-th indexed bit of each player is drawn i.i.d. from μI while other bits of players are all drawn i.i.d. from Nlo
Lemma B.5. (e-DIFFDIST communication bound, Srinivas et al. (2022)). The communication complexity of solving the e-DIFFDIST problem with constant p probability under the broadcast model, for any E [0, 0.5), is 0
Note that lower bound for the broadcast model is also lower bound for the message-passing model. By regarding different days servers and bits cost streams of experts, if we generate bits from either case A or case B, then the algorithm needs to distinguish between case and case B to obtain regret at most We design Algorithm 6 to connect the e- E-DIFDIITT with the distributed experts problem. Algorithm (o givee reduction from e-DIFFDIST, and thus we obtain our lower bound in Theorem 5.5 The additional T's factor is from requirement that obtain approximation to the actual cost for the selected expert on each day. We present the complete proof as follows:
2+ 22 ln (24) and p = 3.4 Algorithm can indeed solve EDIIFDIST with probability at least 3. The proof extends naturally to any constant 6, < $
Proof.
We will prove this by showing for
'The proof follows Srinivas et al. 2022 with different model and objective.
20

---

Algorithm 6 An algorithm that reduces the e-DIFFDIST to the summation-based distributed experts problem in the broadcast model.
Input: {x+ X', .... .''".....'""" )."). where X E [0, for all t E [2'] is a binary vector generated from
c-DIFFDIST; Oracle algorithm A that solves the summation-ban based distributed experts problem with regret R and probability larger than 5;
Let 22 (24), R(c+ 1) 1/2:
Cost definition: For day t, we randomly sample a server j and define Lj = X and 17. 0, A5' E (s//U)
Initialize Mo as the initial memory state on the coordinator for A, counter C = 0;
for t 1 to T do
Obtain the actual cost I(t) A(M incurred by A:
++ I(t):
Update memory state to Mr by communicating with downstream servers according to A;
Let C & be the average cost;
Ô > 1-Re then
Return Case A;
Case
else
Return Case
We further need R <
1)++1 to make sure + c is a valid probability. Let Ò' be the average cost of A. We will show we can solve the e-DIFFDIST problem in both cases.
1
For case A, E' is just the average of 'T i..dd. coin flips. Thus, by Hoeffding's ' inequality we have:
Pr à < 1- Rc
Ò2 1+ Re
Pr 1 1-
2
TR26
exp
2
6² 2
exp
1
3
where the third line is due to TR² 2 1.
For case B, let C* be the average cost of the expert whose cost is generated from μl1 Bernoulli
R(c + 1)). As we know, A has the guarantee that C s C + R with probability at least 3 4, so we have:
Pr > I-Rc)
Pr
Ô C* + R U (C* R 1- Re
Pr Ö C* + R) +Pr RR> L-Re)
IA
1 + Pr (0* > -[(c+1)
+ exp TR22
Thus we have shown that we can solve the DIDIFFDIST problem in both cases with probability at least 3. and therefore make Algorithm 6 valid reduction. As a result, the total communication cost of Algorithm 6 is least 12( # by Lemma B.5 In addition, if we need know the cost of the selected expert, we need to pay extra ((s) communication per day. Indeed, we need ((s) communication even if we just want to verify whether the selected expert incurs zero cost or not with probability larger than 9 10 This is due to the fact that we can choose our distribution so that on each day, we choose a random server and with probability 1/2 make the cost 0 on that server, while with the remaining probability 1/2 we make the cost 1 on that server. All other servers have cost O. Thus, if the protocol probes o(s) servers on each day, it only has a 1/2 + o(1) probability to know the cost is non-zero not. Thus, we need to at least probe ((s) servers succeed with constant
21

---

probability on single day. and since the days are independent, (((TT)) communication in total. Thus, we overall have a communication lower bound of D バ² Ts).
Since we allow each server to have M = = &T + 1) memory, we can actually save communication for messages sent between the same server but on different days. However, the communication required can be reduced by at most s. Let Cost(A) be the communication cost for A. We then +T's,, we thus have Cost(AA) S2( A +T's).
have Cost(AA)+ A)+TMM E Q2 Re +T's). As A'M O R which completes the proof.
For the maximum/lp norm aggregation function in the broadcast model, we can use the same proof with the same bound since the maximum/f, norm operation gives us the same cost streams as the summation operation under our setting where one random server has cost X while others have zero costs.
C Comparison with Kanade et al. (2012)
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 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 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 well. In addition, IKnnaee 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 = 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 for the case when only the coordinator can initiate conversation and Table for the case when both the coordinator and servers can initiate conversation.
Table 5: Coordinator initiates message- message-passing channel
Lower Bound
Upper Bound
12nn/ R + Ts) and oblivious adversaries
Ours
Ö(n/R²² Ts)
01 for n 2 and adaptive adversaries
Kanade et al. 20122
Not applicable
Table 6: Coordinator or server initiates message-passing channel
Lower Bound
Upper Bound
Q(n/R*) R*) for any
Ours
Ö(n/R²)
and oblivious adversaries
Kanade al. (2012)
Not applicable
Not applicable
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. 2202)'s 's upper bound is not applicable in our setting as it assumes the cost (payoff vector) to be distributed only one server. At the same time, we allow the cost to be distributed to any number of servers. Thus, their setup is 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 Ō (())).
). In short, our results are incomparable as we allow: 1. Costs to be distributed any number of servers Any n for the
lower-bound proof against oblivious adversaries rather than adaptive adversaries.
22

---

Table 7: Communication costs of constatt-probabilityy protocols on Gaussian distribution in different settings. We use EWA as the comparison baseline.
ALGORITEMS
EWA
ExP3
DEWA-S
BASE-S
DEWA-M 1/
BASE-M I/ 0.0145x
SAMPLING BATCH&
BROADCAST (Now SPARSE)
MLLSAGE-PASSINN INDN-SPARSI
1x
0.0196X
0,0104X 0.1298K
0.0104x
0.0000
0.7328
MESSAGE PASSING (SPARSE)
BROADCAST (ShARSE)
1x
0.0196x
0.0089X 000000X
0,010HX 0.0288x
0,0100X 70.0188x
0.0039% / 0.0198x
D Simulated Experiments
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 be 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 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 8. To show the robustness of our protocols under extreme cost conditions, we also evaluate 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 number of servers to be s 50, the number of experts be n 100, and the total days to be T = 10 for b = 1 and to be T = 10 for b = n. We set the sampling budget b. = 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 17-12700K Processor and 32GB RAM.
and with Exp3 when be 1. We further evaluate two
0.1, the
D.1 Baselines
For baselines to be compared, 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 2, is then defined as:
72.8
Σ be
where af, Bernoulli ),, 8 Bernoulli 2). This is good baseline to compare with since i is also an unbiased estimator. However, due to the uniform sampling strategy, BASE-S will fail in the sparse setting and require additional factor of 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 4f. To illustrate the effectiveness of DEWA-M, we enforce that the overall communication cost for BASE-M is close to DEWA-M when b. = 1 or b.
D.2 Results of Gaussian Distribution Cost
In Figure 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 be 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, = 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. 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
23

---

Table 8: Communication costs of high-probability protocols Gaussian distribution in different settings. We use EWA as the comparison baseline.
ALGORITEMS
EWA
EXP3
DEWA-S-P
BASE-S-P
DEWA-M-P 1/
BASE-M-P L/n
SAMPLING BATCH&
BROADCAST (NON SPARSE)
MLLSACE-AASSINN INDA-SPARSII
1x
0.0196X
0.482 70.822X
0.6943X 0.7626K
0,0781X 1973
0,0729X / 0.7718X
MESSAGE PASSING (SPARSE)
BROADCAST (ShARSE)
1x
0.0196X
0.4828X 70.8225
0.4945X 0.7625x
0.0696 7008822
0,0706X / 00.1182X
Enga
EWA
BASES
BASESS
BASE-S-P
Regnet
0:1
DEWA-S
Rogret
0.1
DIFRIA-S
3,03
0.7
(a) Regret be
1.
(h) Regret b.
Figure 3: Regrets on Gaussian distribution with summation aggregation, non-sparse scenario.
effective and can handle such extremely sparse cost conditions, As expected, the high-probabilitty 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 Figure 6 The regrets of DEWA-M and DEWA-M-P are close to EWA when b n, and their performance much better than Exp3 when b = 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-PP when b. n, shown in Table and Table 8 Consistent with our findings for the summation aggregation function. in the sparse setting, the regrets of BASE-M and BASE-M 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 i.idd 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 7 and for a high probability guarantee in Table We use the communication cost of EWA as the baseline (1x), which Ö + Ts). According our results, for b. and b. 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 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 DEWAA-M, and DEWA-M-P are more consistent across settings. By increasing b., the protocols achieve lower regret at the cost of more communication. Users can choose b. according to their regret requirements and communication budget. Even if we set b = n, communication costs are still much smaller than that of EWA, but the regret of our algorithms is very close to optimal.
D.3 Results of Bernoulli Distribution Cost
In this section, we present our regret and communication on Bernoulli distributed costs. Our regrets are shown in Figure Figure g Figure and F0 and our communication costs are presented in and Table 10 which are consistent with our observations for Gaussian distribution. DEWA-S DEWWA-SPP. DEWA-M. and DEWA-M-P all perform well in both non-sparse and sparse scenarios, with ncar-optimal regrets and much smaller communication costs compared with the EWA.
Table annd
24

---

Expd BASE-S
EWA BASE-S
BASE-S DEWA-S DIERA S-P
BASE S.P
Rogrot
Regret
6.1
DEWA-S
DEWA-S-
0.08
345
400
-10"
(a) Regret be 1.
(b) Regret be = 71
Figure 4: Regrets on Gaussian distributions with summation aggregation, sparse scenario.
Exp3
BWA BASE-M
BASE-
0.23
BASE M-P
BASE MEP
0.12
DEWA-M
DEWA M
Regret
DEWA
Regres
DEWA M.P.
6.1
10
10"
(a) Regret be = 1.
(b) Regret b. = n.
Figure 5: Regret on Gaussian distribution with maximum aggregation, non-sparse scenario.
Exp3
BASC M
BASE-M-P DEWA, M
DEWA-M
Regeet
DEWA M-P
Regges
DEWA M.P
(a) Regret b. 1.
(b) Regret = 7.
Figure 6: Regret Gaussian distribution with maximum aggregation, sparse scenario.
Table 9: Communication costs of constant-probablle protocols on Bernoulli distribution in different settings. We use EWA as the comparison baseline.
ALGORITEMS
EWA
EXP3 SUM MAX
DEWA-S
BASE-S SUM
DEWA-M MAX 1/R
BASE-M
ArG PUNK
SUM MMAX
MAX L/n
BATCH
(NON-SPARST)
70.086X
MESSACE-PASSING (PARSSPA
BROADCAST (SPARSE)
MESSALE-AAAA PASSING (SPARSE)
1x
0.0196X
0.0099 0000166
0.0104X 0.02988
0.0089x 70.010xx
0.0089X 0.0198x
Table 10: Communication costs of high- probabiitb protocols on Bernoulli distribution in different settings. We use EWA as the comparison baseline.
ALGORITEMS
EWA
EXP3 SUM MAX
DEWA-S-P SUM
BASE-S S.P SUM
DEWA M MAX
BASE M.P MAX 1/
AUG. PUNC
SUM / MAX
SPARSE]
BROADCAST (SPAREE
MESSAGR-PASSIE (SPAESE)
1x
0.0196X
0.4827 70
0.4945 0.7626x
BAR897 700979X
0L8700GK 0.118x
25

---

0.03
Eagd
EWA DEWAA- DERA-SSPP
022
RASE-S-P DEWA-S DEWA-S-PP
Regret
0.23
Rogret
0:1
0.2
0.4
0.0
0.5
0.2
(a) Regret
Regret 71
Figure Regrets on Bernoulli distribution with summation aggregation, non-sparse scenario.
Esp3
EWA
BASE-S
BASE S
0.2
RASE-S-P
0.2
BASE-S-P
DEWAA
DEWA-S
Regret
DEWA-S-P
Regret
3.15
DEWA-S.P
0.1
0.00
340
(a) Regret b. 1.
(b) Regret = n.
Figure Regrets on Bernoulli distribution with summation aggregation, sparse scenario.
Exp3 BASE M RASEM-P
EWA
03-
BASE-M
BASE--P
DEWA M
0.1
DEWA M
Regret
0.2
DEWA-M-P
Regret
DEWA-M-P
0.1
40
(a) Regret b. 1.
(b) Regret b. = n.
Figure 9: Regret on Bernoulli distribution with maximum aggregation, non-sparse scenario.
Exp3 BASE-M
0.23
BWA
BASE-M
BASE-M-P
BASE-MPP
DEWA M DEWA-M-P
DEWA M
Regret
Regret
3.15
DEWA-MPP
0405
107
(a) Regret b, = 1.
(b) Regret = n.
Figure 10: Regret on Bernoulli distribution with maximum aggregation, sparse scenario.
D.4 Evaluation Results under Different
To further study the influence of b. on our algorithms, we evaluate the regret and communication cost of DEWA-S-P and DEWA-M-P under different b., ranging from regret results can be found in Figure 11 As expected, using larger b, makes the regret converge faster. We observe that using a reasonably large value (0.25m in our experiments) sufficient to achieve good regret. The resulting communication cost using different b, can be found in Figure T2 As expected, the cost generally grows linearly with respect to increasing be.
100. The results on the
26

---

0.150
0.13
0.I
0.1m
0.1
0.25
Regret
0.25%
0.08
6.1
40
(a) DEWA-S-P.
(b) DEWA-M-P.
Figure 11: Regret for Gaussian distribution under different be, non con-sparse scenario.
DEWA-S-P
Communication cost
055
DEWA MP
0.9
1133
Figure 12:
Communication cost of DEWA-S-P and DEWA-M-P using different b,, and with EWA as the baseline, non-sparse scenario.
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Claims are included
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer:
[Yes]
Justification:
The lower bound is conditional.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
27

---

The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: Please refer to each individual claims and proofs.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: source code included the supplementary materials
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed
28

---

instructions for how to replicate the results, access to a hosted model (e.g., g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (c.g.. a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how construct the dataset).
(d) We recognize that reproducibility may tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. the case of closed-source models, it may be that access to the model is limited in some way (e.g.. registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: provide running scripts for all experiments in the paper
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
mublcc/guides/Cddelbbbii.ss
otw.ooddeSsbmiiiioooooooosoo snooiyicy)) for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/Ct////ooeeeeeeeeeeeeeeeeee ssiocclicyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: please refer Appendix D
Guidelines:
The answer NA means that the paper does not include experiments.
29

---

The experimental setting should be presented in the core of the paper to level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: our results are averaged over multiple runs and variance hars are plotted
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: please refer to Appendix D
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics httpp://eerriiscccppiii//hhcccce
Answer: [Yes]
Justification: Not applicable
Guidelines:
30

---

The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: communication savings
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymeent of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Not applicable
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
31

---

Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: citations are properly added Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, wwwpppwipaahtaeea thcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if has changed) should be provided. If this information is available online, the authors are encouraged to reach out the asset's ss creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Not applicable
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Not applicable
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
32

---

Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Not applicable
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
33


Reviews:
[{"review_id": "bwND2jyTXR", "reviewer": "Reviewer_FQkW", "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?\n\nAs 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}})$)?\n\nThis 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$.  \n\nThis 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.", "questions": "- What is the argument for why the broadcast communication model is reasonable for this particular problem (not other distributed problems)?\n\n- 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": "This is fine.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Overall, I like this paper and would advocate acceptance, although it has a few weaknesses.  But fundamentally, it's an interesting problem and they give reasonable results.\n\n- The motivating example of distributed online optimization seems quite reasonable to me, and more generally I like the idea of \"evaluating different experts requires talking to many different servers\".  While there has been previous work on \"distributed experts\", this paper is (to the best of my knowledge) the first to study this particular setting.\n\n- The given algorithms are reasonably simple, which is great, but are not obvious.  The main idea is that we need to evaluate the quality of an expert without actually querying every server about them.  They do this probabilistically, getting an unbiased estimator of the cost of each expert for very cheap and then using this estimator.  This has some of my favorite type of analysis, where the math isn't \"hard\", but there are clever and non-obvious ideas.", "weaknesses": "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.  \n\n- 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.\n\n- 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*.\n\n- The writing in this paper is quite poor, in a few different ways.\n  - 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.\n  - 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).  \n  - 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.\n  - 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?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their review and address their main concerns below.\n\n**Q1. Motivation for the Broadcast Model**\n\nWe thank the reviewer for acknowledging the setup for the message-passing model. For the broadcast model, there are fewer scenarios for the distributed experts problem than in the message-passing model, but there are still several important ones. Imagine a multi-level distributed online learning setting, where the upper-level consists of message-passing models while the lower-level in the hierarchy is a one-hop wireless model. For example, consider an online federated learning setting in which the end servers are edge devices such as cell phones. Our algorithm can be used in different levels within the hierarchy based on different communication models to achieve optimal performance. Additionally, a satellite communication model is another scenario in which the broadcast model is important. Other than practical motivations, the broadcast model is a well-studied model [1, 2] across different domains including streaming [3, 4, 7], cryptography [5], and mechanism design [6]. We therefore introduce the broadcast model for the distributed experts problem and provide optimal communication and regret tradeoffs under various aggregation functions such as the maximum and the $l_p$ norm.\n\n**Q2. Lower Bound**\n\nWe thank the reviewer for pointing out our memory assumption on the lower bound. First, we note that our memory bound is only imposed on downstream servers. We also note that our lower bound is against the weakest possible adversary (oblivious adversarial) and thus holds in the most general setting. Here we obtain an $O(\\frac{n}{sTR^2}+1)$ bound, which for  the near-optimal regrets $R \\in [O(\\sqrt{\\frac{\\log{n}}{T}}), O(\\sqrt{\\frac{n\\log{n}}{T}})]$ we consider, we have that the $\\frac{1}{\\sqrt{T}}$ term cancels with the $T$ in our $TR^2$ bound. We will make the memory bound clearer in our revision to avoid unnecessary confusion.\n\n**Q3. Writing**\n\nWe thank the reviewer for pointing out the issues in our presentation. The communication bound for DEWA-S is derived in Section 4.2, but we will also include the formal theorem and proof of the communication bound for DEWA-S to align with DEWA-M and DEWA-L. We will also make the notation of the paper clearer and more consistent. \n\n**References:**\n\n1. Braverman, Mark, and Rotem Oshman. \"On information complexity in the broadcast model.\" Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing. 2015.\n\n2. Kushilevitz, Eyal. \"Communication complexity.\" Advances in Computers. Vol. 44. Elsevier, 1997. 331-360.\n\n3. Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments. Journal of Computer and System Sciences, 58(1):137 – 147, 1999.\n\n4. Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, and D. Sivakumar. An information statistics approach to data stream and communication complexity. J. Comput. Syst. Sci., 68(4):702–732, 2004.\n\n5. Shahar Dobzinski, Noam Nisan, and Sigal Oren. Economic efficiency requires interaction. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing, STOC ’14, pages 233–242, 2014.\n\n6. Oded Goldreich and A Warning. Secure multi-party computation. unpublished manuscript, 1998.\n\n7. André Gronemeier. Asymptotically optimal lower bounds on the NIH-multi-party information complexity of the AND-function and disjointness. In Proc. 26th Symp. on Theor. Aspects of Comp. Sc. (STACS), pages 505–516, 2009", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KeSip7xfHM", "reviewer": "Reviewer_B3J6", "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.", "questions": "I do not have any questions.", "limitations": "Not applicable.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "It performs a set of interesting theoretical exercise to a fundamental expert problem in the distributed setting. Techniques developed in this work are useful addition to this area.", "weaknesses": "I feel more effort is needed to make this paper a smoother read for both theoreticians and general audience.\n\nSome (writing) issues I found: \n\n1. 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.\nFor the broadcasting setting, how is cost counted? Number of broadcasts? \n2. 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. \n3. 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)$. \n4. 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?  \n\nThose are all quite minor stuff so I wish the authors could make some effort to clear them up.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their review and address their main concerns below.\n\n**Q1. Presentation**\n\nWe thank the reviewer for pointing out the issues in our presentation. \n\nThe problem is indeed an experts problem as we assume each server can observe the full cost vector. The reason we introduced the multi-arm bandit problem in the related work is that the optimal algorithm (Exp3) proposed for the multi-arm bandit problem can serve as one possible solution for our problem and thus a baseline that we can compare with.\n\nWe thank the reviewer for pointing out the inconsistency of assumptions on $R$ between the different tables. In the last paragraph of Section 1 we mention the assumptions: we assume $R \\in [ \\tilde{O}  ( (\\frac{\\log n}{T} )^{\\frac{\\varepsilon}{1+\\varepsilon}}  ), \\tilde{O}  ( (\\frac{n\\log n}{T} )^{\\frac{\\varepsilon}{1+\\varepsilon}}  )  ]$ for DEWA-L as well as DEWA-L-P when $1+\\varepsilon < p \\leq 2$, and $R \\in  [\\tilde{O}(\\sqrt{\\frac{\\log{n}}{T}}), \\tilde{O}(\\sqrt{\\frac{n\\log{n}}{T}}) ]$ for the others. We will make the regret bound clearer and more consistent across all tables.\n\nWe thank the reviewer for pointing out the notational confusion. The reason why we write the regret R to be in a range is that our algorithm allows for a hyper-parameter $b_e \\in [n]$, which can be specified to give a tradeoff between the regret and the communication cost. Depending on the different choice of $b_e$ our algorithm can achieve a corresponding optimal regret $R=O(\\sqrt{\\frac{n\\log{n}}{T b_e}})$. Thus, given that $b_e \\in [n]$, the optimal regret $R will be in $[O(\\sqrt{\\frac{\\log{n}}{T}}), O(\\sqrt{\\frac{n\\log{n}}{T}})]$ accordingly. To avoid confusion, we will make this point clearer in the preliminaries.\n\n**Q2. Memory bound**\n\nWe thank the reviewer for pointing out our memory assumption on the lower bound. First, we note that our memory bound is only imposed on downstream servers. We also note that our lower bound is against the weakest possible adversary (oblivious adversarial) and thus holds in the most general setting. Here we obtain an $O(\\frac{n}{sTR^2}+1)$ bound, which for  the near-optimal regrets $R \\in [O(\\sqrt{\\frac{\\log{n}}{T}}), O(\\sqrt{\\frac{n\\log{n}}{T}})]$ we consider, we have that the $\\frac{1}{\\sqrt{T}}$ term cancels with the $T$ in our $TR^2$ bound. We will make the memory bound clearer in our revision to avoid unnecessary confusion.\n\nThe memory constraint on each server will indeed become stronger as the number of servers increases due to more communication required to achieve the optimal regret. It is a challenging open question to completely remove this assumption. On the other hand, notice that the overall memory requirement for all servers is $O(\\frac{n}{TR^2}+s)$ which increases linearly as we have more servers. This does model situations in which the memory budget is constant for each server.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xdUBTrAwLw", "reviewer": "Reviewer_eSR8", "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.\n\nThe 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.\n\nThe proposed algorithms leverage sampling techniques to approximate the aggregated functions and reduce communication overhead.", "questions": "Could you move the discussion comparing your work with the Kanade et al. paper into the main text?\n\nCould you provide more justification for selecting the 'max' function as one of the aggregation functions in your study?", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper examines an important problem, thoroughly covering upper bounds, lower bounds, and empirical evaluations.", "weaknesses": "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.\n\nThe paper considers two aggregation functions: sum and max. The selection of max, however, seems a bit odd and lacks clear motivation.\n\nThe 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their review and address their main concerns below.\n\n**Q1. Comparison with Kanade et al.**\n\nWe thank the reviewer for the suggestion. We will move the comparison with Kanade et al. to the main text in a revision, as we indeed consider it very relevant to our work.\n\n**Q2. Max aggregation function**\n\nThe maximum aggregation function is usually used when the objective is dependent on the worst cost across different servers, e.g., if the objective is to lower the worst case serving latency for some downstream tasks to satisfy certain SLOs (Service Level Objectives), or we want to bound the maximum drawdown for a diversified investment across different regions. Notice that besides the summation and maximum aggregation function, we also support the $l_p$ aggregation function, which is a much more general aggregation function, where the maximum function is a very special case $l_\\infty$ as we assume all costs are positive. We believe the $l_p$ aggregation function protocols also introduce several interesting technical ideas. \n\n**Q3. Memory bound assumption**\n\nWe thank the reviewer for pointing out our memory assumption on the lower bound. First, we note that our memory bound is only imposed on downstream servers with no memory bound assumption on the central coordinator. We also note that our lower bound is against the weakest possible adversary (oblivious adversarial) and thus holds in the most general setting. On the other hand, notice that the overall memory requirement for all downstream servers is $O(\\frac{n}{TR^2}+s)$ which increases linearly as we have more servers. This does model situations in which the memory budget is constant for each server.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5mnDpjxTIn", "reviewer": "Reviewer_rqWP", "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.", "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. \n\n1. 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.\n\n2. 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": "Yes.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 1, "strengths": "It is an interesting idea to consider the distributed version of this classical problem, especially as applications of distributed continue to grow. The use of randomization in max aggregation and $\\ell\\_lp$ norms (through exponential random variable) is interesting.", "weaknesses": "The novelty of the paper especially in terms of analysis is limited. The analysis of all the algorithms is largely based on existing results. \n\nPlease refer to the next section for additional questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their constructive comments and address the main concerns below.\n\n**Q1. The coordinator assumption**\n\nWe agree with the reviewer that in some scenarios there does not exist a coordinator to coordinate the communications among downstream servers. The motivation for the coordinator initialization assumptions is: 1. to avoid the complexities in asynchronous communications, e.g., handshake protocols or extra buffers to guarantee ordering; 2. the coordinator is commonly seen in both message-passing and broadcast models in practice as well as theory [1, 2]. Additionally, for the case where the coordinator does not need to initiate communication, we can achieve an $O(b_e \\log{(s/\\delta)})$ communication cost per time step with the following protocol: Initialization: each individual server initializes a $\\hat{h_i^t}$ to record the maximum cost for each expert. 1. For each server who has a cost larger than the current maximum, send its value to the broadcast channel after a $\\delta_{i, j}$ time delay, where $\\delta_{i, j}$ is randomly sampled from $[0, 1]$. 2. Once the broadcast channel has been occupied, all other servers stop the sending action and update their corresponding $\\hat{h_i^t}, \\delta_{i, j}$ instead. Then we can repeat this process and use the maximum value collected after $s$ unit time steps as an estimate to the maximum value. In this protocol, we assume that the broadcast channel can only be occupied by one server. The random ordering is guaranteed by the random delay and the expected number of communication rounds to get the maximum value is given in Lemma B.1. Additionally, notice that for each time step the protocol is guaranteed to end within $s$ time steps as the worst case delay is 1 unit time step for each server. By using this protocol, we can still obtain a near optimal communication cost of $O(b_e \\log{s/\\delta})$. We thank the reviewer for bringing this up and inspiring us to design a new protocol under different assumptions. We will add the new results and setups in the next version.\n\n**Q2. Sparsity for the summation aggregation function**\n\nFirst we want to point out that normalizing a cost vector to $l_i^t \\in [0, 1], l_{i, j}^t \\geq 0$ is a common practice in the experts problem literature. The way we distribute $l_i^t$ to different servers is purely random, which does not impose any sparsity assumption. In fact, even if $l_i^t \\in [0, \\rho], l_{i, j}^t \\geq 0, \\forall \\rho > 0$, the communication upper bound for our algorithm will not change as our sampling probability (more specifically $\\beta_{i, j}^t$) is designed to be $\\frac{l_{i, j}^t}{\\rho}$, and then the communication cost is proportional to $b_e \\cdot T \\cdot \\frac{\\sum_{j=1}^s l_{i, j}^t}{\\rho}$, where $\\frac{\\sum_{j=1}^s l_{i, j}^t}{\\rho} \\in [0, 1]$. As we have assumed that $\\rho=1$ in our setup without affecting the optimality, we have ignored the $\\rho$ factor during our derivation, which might cause the confusion. We thank the reviewer for pointing this out and will make our definitions and explanations clear to avoid potential confusion.\n\n**References:**\n\n1. Kanade, Varun, Zhenming Liu, and Bozidar Radunovic. \"Distributed non-stochastic experts.\" Advances in Neural Information Processing Systems 25 (2012).\n\n2. Braverman, Mark, and Rotem Oshman. \"On information complexity in the broadcast model.\" Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing. 2015.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

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