Adaptive Communication Bounds for Distributed Online Learning
This work addresses communication efficiency in distributed learning systems, but it appears incremental as it builds on a previously published protocol.
The paper tackles the trade-off between learning performance and communication efficiency in distributed online learning, showing that a simplified version of a known protocol meets formal criteria for adaptive communication bounds based on problem hardness.
We consider distributed online learning protocols that control the exchange of information between local learners in a round-based learning scenario. The learning performance of such a protocol is intuitively optimal if approximately the same loss is incurred as in a hypothetical serial setting. If a protocol accomplishes this, it is inherently impossible to achieve a strong communication bound at the same time. In the worst case, every input is essential for the learning performance, even for the serial setting, and thus needs to be exchanged between the local learners. However, it is reasonable to demand a bound that scales well with the hardness of the serialized prediction problem, as measured by the loss received by a serial online learning algorithm. We provide formal criteria based on this intuition and show that they hold for a simplified version of a previously published protocol.