99% of Parallel Optimization is Inevitably a Waste of Time

By Konstantin Mishchenko, Filip Hanzely, Peter Richtárik. 2019

13 citations recorded by the source corpus.

It is well known that many optimization methods, including SGD, SAGA, and Accelerated SGD for over-parameterized models, do not scale linearly in the parallel setting. In this paper, we present a new version of block coordinate descent that solves this issue for a number of methods. The core idea is to make the sampling of coordinate blocks on each parallel unit independent of the others. Surprisingly, we prove that the optimal number of blocks to be updated by each of $n$ units in every iteration is equal to $m/n$, where $m$ is the total number of blocks. As an illustration, this means that when $n=100$ parallel units are used, $99\%$ of work is a waste of time. We demonstrate that with $m/n$ blocks used by each unit the iteration complexity often remains the same. Among other applications which we mention, this fact can be exploited in the setting of distributed optimization to break the communication bottleneck. Our claims are justified by numerical experiments which demonstrate almost a perfect match with our theory on a number of datasets.

Subfields: Artificial Intelligence, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

Citations in the corpus

Natural Compression for Distributed Deep Learning (2019, background): “Another possibility is to apply randomized sparsification masks to the gradients [45, 28, 4, 44], or to rely on coordinate/block descent updates-rules, which are sparse by design [37, 11, 32].”
Stochastic Distributed Learning with Gradient Quantization and Variance Reduction (2019, methodology): “An alternative approach is not to compute the gradient and subsequently compress it, but to update a subset of elements of the iterate x using coordinate descent type updates (Richt´arik & Tak´aˇc, 2016; Fercoq et al., 2014; Mishchenko et al., 2019).”
Unified Analysis of Stochastic Gradient Methods for Composite Convex and Smooth Optimization (2020, methodology): “While quantized stochastic gradient methods have been widely used in machine learning applications, it was not until the DIANA algorithm [26, 27] that a distributed method was shown to converge to the neighborhood of a minimizer for strongly convex functions.”
One Method to Rule Them All: Variance Reduction for Data, Parameters and Many New Methods (2019, methodology): “On the other hand, ISEGA [20] does not have the issue, but it requires a computation of the exact partial derivatives on each machine and thus is expensive.”
A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descent (2019, background): “6 is a special case of Lemmas 3,4 from [21] without prox term.”