Better Bounds for the Distributed Experts Problem

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 _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 R1Tpoly(nsT), using O(nR^2+sR^2)(s^1-2/p,1)poly(nsT) bits of communication, which improves on previous work.

Reproductions