Better Bounds for the Distributed Experts Problem

arXiv:2603.09168v1 Announce Type: cross
Abstract: 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 $ell_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 $Rgtrsimfrac{1}{sqrt{T}cdottext{poly}log(nsT)}$, using $mathcal{O}left(frac{n}{R^2}+frac{s}{R^2}right)cdotmax(s^{1-2/p},1)cdottext{poly}log(nsT)$ bits of communication, which improves on previous work.