Data-Distributed Weighted Majority and Online Mirror Descent
  In this paper, we focus on the question of the extent to which online
learning can benefit from distributed computing. We focus on the setting in
which $N$ agents online-learn cooperatively, where each agent only has access
to its own data. We propose a generic data-distributed online learning
meta-algorithm. We then introduce the Distributed Weighted Majority and
Distributed Online Mirror Descent algorithms, as special cases. We show, using
both theoretical analysis and experiments, that compared to a single agent:
given the same computation time, these distributed algorithms achieve smaller
generalization errors; and given the same generalization errors, they can be
$N$ times faster.
