Distributed Stochastic Variance Reduced Gradient Methods and A Lower Bound for Communication Complexity

Abstract

We study distributed optimization algorithms for minimizing the average of convex functions. The applications include empirical risk minimization problems in statistical machine learning where the datasets are large and have to be stored on different machines. We design a distributed stochastic variance reduced gradient algorithm that, under certain conditions on the condition number, simultaneously achieves the optimal parallel runtime, amount of communication and rounds of communication among all distributed first-order methods up to constant factors. Our method and its accelerated extension also outperform existing distributed algorithms in terms of the rounds of communication as long as the condition number is not too large compared to the size of data in each machine. We also prove a lower bound for the number of rounds of communication for a broad class of distributed first-order methods including the proposed algorithms in this paper. We show that our accelerated distributed stochastic variance reduced gradient algorithm achieves this lower bound so that it uses the fewest rounds of communication among all distributed first-order algorithms.

significant addition to both theory and experimental results

References in corpus (6)

• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• Communication Complexity of Distributed Convex Learning and Optimization
• Communication-Efficient Distributed Dual Coordinate Ascent
• Finito: A Faster, Permutable Incremental Gradient Method for Big Data Problems
• Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization
• An optimal randomized incremental gradient method

Cited by in corpus (26)

• Federated Optimization: Distributed Machine Learning for On-Device Intelligence
• SCAFFOLD: Stochastic Controlled Averaging for Federated Learning
• Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates
• Byzantine Stochastic Gradient Descent
• A Unified Theory of Decentralized SGD with Changing Topology and Local Updates
• Efficient Distributed Learning with Sparsity
• Faster On-Device Training Using New Federated Momentum Algorithm
• Quasi-Global Momentum: Accelerating Decentralized Deep Learning on Heterogeneous Data
• Stochastic, Distributed and Federated Optimization for Machine Learning
• GIANT: Globally Improved Approximate Newton Method for Distributed Optimization
• Gradient Diversity: a Key Ingredient for Scalable Distributed Learning
• Without-Replacement Sampling for Stochastic Gradient Methods: Convergence Results and Application to Distributed Optimization
• Communication trade-offs for synchronized distributed SGD with large step size
• Stochastic Nonconvex Optimization with Large Minibatches
• Defending Against Saddle Point Attack in Byzantine-Robust Distributed Learning
• Trading-off variance and complexity in stochastic gradient descent
• DSCOVR: Randomized Primal-Dual Block Coordinate Algorithms for Asynchronous Distributed Optimization
• Random Shuffling Beats SGD after Finite Epochs
• A Provably Communication-Efficient Asynchronous Distributed Inference Method for Convex and Nonconvex Problems
• Straggler-Agnostic and Communication-Efficient Distributed Primal-Dual Algorithm for High-Dimensional Data Mining
• Guaranteed Sufficient Decrease for Variance Reduced Stochastic Gradient Descent
• Distributed Block-diagonal Approximation Methods for Regularized Empirical Risk Minimization
• Optimising cost vs accuracy of decentralised analytics in fog computing environments
• Variance-Reduced Stochastic Learning by Networked Agents under Random Reshuffling
• Larger is Better: The Effect of Learning Rates Enjoyed by Stochastic Optimization with Progressive Variance Reduction
• Communication-efficient Algorithm for Distributed Sparse Learning via Two-way Truncation