Parallelized Stochastic Gradient Descent

TLDR

Parallel machine learning is increasingly pressing due to growing data availability. The paper introduces the first parallel stochastic gradient descent algorithm, providing detailed analysis and experimental evidence. The algorithm offers parallel acceleration guarantees without strict latency constraints, and its analysis employs contractive mappings to quantify convergence speed of parameter distributions. The study demonstrates how quickly stochastic gradient descent reaches the asymptotically normal regime.

Abstract

With the increase in available data parallel machine learning has become an increasingly pressing problem. In this paper we present the first parallel stochastic gradient descent algorithm including a detailed analysis and experimental evidence. Unlike prior work on parallel optimization algorithms [5, 7] our variant comes with parallel acceleration guarantees and it poses no overly tight latency constraints, which might only be available in the multicore setting. Our analysis introduces a novel proof technique — contractive mappings to quantify the speed of convergence of parameter distributions to their asymptotic limits. As a side effect this answers the question of how quickly stochastic gradient descent algorithms reach the asymptotically normal regime [1, 8].