Communication Bounds for the Distributed Experts Problem

We thank the reviewer for their constructive comments and address the main concerns below.

Q1. The coordinator assumption

We 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.

Q2. Sparsity for the summation aggregation function

First 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.

References:

1. Kanade, Varun, Zhenming Liu, and Bozidar Radunovic. "Distributed non-stochastic experts." Advances in Neural Information Processing Systems 25 (2012).

2. Braverman, Mark, and Rotem Oshman. "On information complexity in the broadcast model." Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing. 2015.

We thank the reviewer for their review and address their main concerns below.

Q1. Comparison with Kanade et al.

We 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.

Q2. Max aggregation function

The 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.

Q3. Memory bound assumption

We 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.

We thank the reviewer for their review and address their main concerns below.

Q1. Presentation

We thank the reviewer for pointing out the issues in our presentation.

The 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.

We 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.

We 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.

Q2. Memory bound

We 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.

The 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.

We thank the reviewer for their review and address their main concerns below.

Q1. Motivation for the Broadcast Model

We 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.

Q2. Lower Bound

We 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.

Q3. Writing

We 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.

References:

1. Braverman, Mark, and Rotem Oshman. "On information complexity in the broadcast model." Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing. 2015.

2. Kushilevitz, Eyal. "Communication complexity." Advances in Computers. Vol. 44. Elsevier, 1997. 331-360.

3. 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.

4. 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.

5. 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.

6. Oded Goldreich and A Warning. Secure multi-party computation. unpublished manuscript, 1998.

7. 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