# Better Bounds for the Distributed Experts Problem

arXiv: https://arxiv.org/abs/2603.09168 · HTML: https://mlsanity.com/paper/2603.09168/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 32 references that are in the map.
- First posted on arXiv 10 Mar 2026.

## Builds on (most cited first, 13 of 13)

- [HPO-B: A Large-Scale Reproducible Benchmark for Black-Box HPO based on OpenML](https://mlsanity.com/paper/2106.06257/) (2021)
- [Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning](https://mlsanity.com/paper/1602.05161/) (2016)
- [Stochastic Multi-armed Bandits in Constant Space](https://mlsanity.com/paper/1712.09007/) (2017)
- [Memory Bounds for the Experts Problem](https://mlsanity.com/paper/2204.09837/) (2022)
- [Extractor-Based Time-Space Lower Bounds for Learning](https://mlsanity.com/paper/1708.02639/) (2017)
- [Detecting Correlations with Little Memory and Communication](https://mlsanity.com/paper/1803.01420/) (2018)
- [Exploration with Limited Memory: Streaming Algorithms for Coin Tossing, Noisy Comparisons, and Multi-Armed Bandits](https://mlsanity.com/paper/2004.04666/) (2020)
- [Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators](https://mlsanity.com/paper/2011.07471/) (2020)
- [Online Prediction in Sub-linear Space](https://mlsanity.com/paper/2207.07974/) (2022)
- [Near Optimal Memory-Regret Tradeoff for Online Learning](https://mlsanity.com/paper/2303.01673/) (2023)
- [Improved Space Bounds for Learning with Experts](https://mlsanity.com/paper/2303.01453/) (2023)
- [Online Learning with Limited Information in the Sliding Window Model](https://mlsanity.com/paper/2601.03533/) (2026)
- [Communication Bounds for the Distributed Experts Problem](https://mlsanity.com/paper/2501.03132/) (2025)

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