Communication Bounds for the Distributed Experts Problem
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913637189287936 |
|---|---|
| author | Jia, Zhihao Pang, Qi Tran, Trung Woodruff, David Zhang, Zhihao Zheng, Wenting |
| author_facet | Jia, Zhihao Pang, Qi Tran, Trung Woodruff, David Zhang, Zhihao Zheng, Wenting |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_03132 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Communication Bounds for the Distributed Experts Problem Jia, Zhihao Pang, Qi Tran, Trung Woodruff, David Zhang, Zhihao Zheng, Wenting Machine Learning 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. |
| title | Communication Bounds for the Distributed Experts Problem |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2501.03132 |