Adaptive Communication Bounds for Distributed Online Learning

W e consider distributed online learning protocols that con trol the exchange of information between local learners in a round-based learning scenario. The learning performance of such a protocol is intuitively optimal if app roximately the same loss is incurred as in a hypothetical serial setting. If a pro tocol accomplishes this, it is inherently impossible to achieve a strong communicati on bound at the same time. In the worst case, every input is essential for the lear ning performance, even for the serial setting, and thus needs to be exchanged betwee n the local learners. However, it is reasonable to demand a bound that scales well w ith the hardness of the serialized prediction problem, as measured by the los s received by a serial online learning algorithm. W e provide formal criteria base d on this intuition and show that they hold for a simplified version of a previously pu blished protocol.