Better Bounds for the Distributed Experts Problem
Not on the map. Why?
Abstract (arXiv)
In this paper, we study the distributed experts problem, where n experts are distributed across s servers for T timesteps. The loss of each expert at each time t is the ℓp norm of the vector that consists of the losses of the expert at each of the s servers at time t. The goal is to minimize the regret R, i.e., the loss of the distributed protocol compared to the loss of the best expert, amortized over the all T times, while using the minimum amount of communication. We give a protocol that achieves regret roughly Rgtrsimfrac1√T·polylog(nsT), using Oleft(fracnR2+fracsR2right)·max(s1-2/p,1)·polylog(nsT) bits of communication, which improves on previous work.
Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 13 of its 32 references that are in the map. First posted on arXiv 10 Mar 2026.
Builds on
13 of 32 references.
References · 13
- 2021HPO-B: A Large-Scale Reproducible Benchmark for Black-Box HPO based on OpenMLcited by 75
- 2016Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learningcited by 32
- 2017Stochastic Multi-armed Bandits in Constant Spacecited by 21
- 2022Memory Bounds for the Experts Problemcited by 20
- 2018Detecting Correlations with Little Memory and Communicationcited by 19
- 2017Extractor-Based Time-Space Lower Bounds for Learningcited by 18
- 2020Exploration with Limited Memory: Streaming Algorithms for Coin Tossing, Noisy Comparisons, and Multi-Armed Banditscited by 18
- 2020Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimatorscited by 16
- 2022Online Prediction in Sub-linear Spacecited by 16
- 2023Near Optimal Memory-Regret Tradeoff for Online Learningcited by 15
- 2023Improved Space Bounds for Learning with Expertscited by 5
- 2026Online Learning with Limited Information in the Sliding Window Modelcited by 3
1 more
- 2025Communication Bounds for the Distributed Experts Problemcited by 1
Built on by
Not cited yet.