全球关于SGD并行的首篇论文

Slow Learners are Fast

John Langford, Alexander J. Smola, Martin Zinkevich

Machine Learning, Yahoo! Labs and Australian National University

4401 Great America Pky, Santa Clara, 95051 CA

{jl, maz, smola}@yahoo-inc.com

Abstract

Online learning algorithms have impressive convergence properties when it comes

to risk minimization and convex games on very large problems. However, they are

inherently sequential in their design which prevents them from taking advantage

[13]. Moreover, learning-theory guarantees show that O(1) passes over a dataset suffice to obtain

optimal estimates [3, 2]. This suggests that online algorithms are an excellent tool for learning.

This view, however, is slightly deceptive for several reasons: current online algorithms process

one instance at a time. That is, they receive the instance, make some prediction, incur a loss, and

update an associated parameter. In other words, the algorithms are entirely sequential in their nature.

While this is acceptable in single-core processors, it is highly undesirable given that the number

of processing elements available to an algorithm is growing exponentially (e.g. modern desktop

machines have up to 8 cores, graphics cards up to 1024 cores). It is therefore very wasteful if only

one of these cores is actually used for estimation.

A second problem arises from the fact that network and disk I/O have not been able to keep up with

variants. To our knowledge, this is the first paper which provides theoretical guarantees combined

with empirical evidence for such an algorithm. Previous work, e.g. by [6] proved rather inconclusive

in terms of theoretical and empirical guarantees.

In a nutshell, we propose the following two variants: several processing cores perform stochastic

gradient descent independently of each other while sharing a common parameter vector which is

updated asynchronously. This allows us to accelerate computationally intensive problems when-

ever gradient computations are relatively expensive. A second variant assumes that we have linear

function classes where parts of the function can be computed independently on several cores. Sub-

sequently the results are combined and the combination is then used for a descent step.

A common feature of both algorithms is that the update occurs with some delay: in the first case