Communication Bounds for the Distributed Experts Problem

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

Q1. Writing

We thank the reviewer for pointing out the deficiencies in our presentation. In our revised version, we have unified the presentation of our communication bounds in the tables, as well as in our contributions section at the top of page 3.

Q2. Memory Bounds

For our memory bound condition in the proof of our lower bound, we clarify that we only impose a memory bound on the downstream servers with no memory assumption on the central coordinator. We believe this assumption is both practical and provides a novel solution for bounding the communication of a server with itself across multiple days. A lower bound proof without a memory bound being imposed on downstream servers is indeed more challenging, which we leave as a very intriguing open question.

Q3. Horizon Assumption

The $T \in O(\log{(ns)})$ assumption is only required for our lower bound argument in the message-passing model with maximum aggregation function. The point here is to show that the best we can do in the message-passing model with a maximum aggregation function is the naive EWA, which is the reason why we can only propose an upper bound in the blackboard model when the maximum aggregation function is used.

Q4. Evaluation

As far as we know, our generic distributed experts setup has not been studied before. [1] only studies the setting when the cost is distributed to a single server rather than arbitrarily aggregated across multiple servers. Also, the memory-efficient streaming algorithms in [2, 3] assume a memory bound on the coordinator, which we don’t have. Thus, given our generic setup, we can think of two baselines: EWA, which is known to achieve optimal regret, and EXP3, which uses less communication and can achieve near-optimal regret. Regarding HPO-B, we have cited the paper in the third paragraph of the introduction. For further clarification, we also cite this benchmark in our evaluation section as well in the revised version of our paper. We have further added more description of our experimental setup and an ablation study on the hyperparameter $b_e$ in the appendix of our revised paper. This demonstrates the communication-regret tradeoff of our methods.

References:

1. Kanade, Varun, Zhenming Liu, and Bozidar Radunovic. "Distributed non-stochastic experts." Advances in Neural Information Processing Systems 25 (2012).
2. Srinivas, Vaidehi, et al. "Memory bounds for the experts problem." Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. 2022.
3. Peng, Binghui, and Fred Zhang. "Online prediction in sub-linear space." Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics, 2023.

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

Q1. Problem Definition and Practical Scenarios

We have highlighted the motivating examples in our introduction and describe them here. For distributed online learning problems (e.g., online federated learning), you can try different sets of hyperparameters that correspond to different experts in the distributed experts problem. The goal is to adaptively choose the optimal hyperparameters on each day. A central coordinator is commonly used in such scenarios, which receives information from users along edges, and updates their model locally. If it is fully decentralized and has point-to-point communication, our communication upper bounds will still hold up to a multiplicative constant factor of 2 (and additive log(# servers)), since the coordinator can forward a message from one server to any other server. Otherwise, our communication bound depends on the specific communication topology, which is not the focus of our paper. In addition, for distributed online learning or federated learning, it is common for the coordinator to commit to the same model due to fairness and privacy issues as well as the memory overhead of storing multiple models for each downstream server.

Q2. Presentation

We thank the reviewer for pointing out the deficiencies in our presentation. We have updated the writing accordingly in the revised version of our paper.

Q3. Evaluation

We have evaluated our methods against real-world data trace (HPO-B) in section 6 and provided simulation evaluations in the appendix to demonstrate that our upper bound methods are robust even against extreme cost distributions (i.e., very sparsely distributed), which do not have corresponding real-world data traces.

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

Q1. Major Contribution

We thank the reviewer for acknowledging the definition of the distributed experts problem as interesting and novel.

Regarding our technical contribution, we agree with the reviewer that our constant probability upper bound with a summation aggregation function (i.e. DEWA-S) is intrinsically an unbiased sampling method, and the proof is mostly similar to that in the non-distributed setting. However, in order to achieve a high probability guarantee, we propose a novel hierarchical EWA algorithm, where each i.i.d. subroutine DEWA-S or DEWA-M can be regarded as a meta-expert. Thus, by running a conventional EWA on top of these meta-experts, we obtain optimal regret with a high probability guarantee (i.e., DEWA-S-P and DEWA-M-P). We note that we also consider the maximum aggregation function in the distributed setting, and here one cannot obtain an unbiased estimator. Instead, we propose a random-walk-based communication protocol that achieves near-optimal regret with constant probability (DEWA-M) or with high probability (DEWA-M-P). To summarize, our algorithms go significantly beyond simple unbiased estimation - we (1) propose a hierarchical EWA algorithm to achieve a high probability guarantee as well as (2) a random-walk-based communication protocol when the maximum aggregation function is used.

Q2. Writing

We thank the reviewer for pointing out the issues in our presentation. We have improved our writing accordingly in our revised submission.

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

Q1. Assumptions post on the range and distribution of the cost

Indeed, the range of the $l_i^t$ can be within $[0, \rho]$ for any $\rho > 0$, and all the regret terms (both upper and lower bounds) will be multiplied by a factor of $\rho$ accordingly. Thus, the upper-bound methods we propose are still nearly optimal. The only reason we make the assumption that $l_i^t \in [0, 1]$ is to simplify the notation in the proof, where we can cancel out the $\rho$ factor. We have updated this description in the revised version of our paper to clarify this confusion (note that changes in the revised version are in blue). Regarding the cost distribution, our upper bound methods are derived against strong adversaries, where the adversary can define the cost vector arbitrarily, while our lower bound proofs hold against oblivious adversaries where the adversary can choose the cost functions arbitrarily but without interacting with the algorithm.