  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.
