Gradient Diversity: a Key Ingredient for Scalable Distributed Learning

Abstract

It has been experimentally observed that distributed implementations of mini-batch stochastic gradient descent (SGD) algorithms exhibit speedup saturation and decaying generalization ability beyond a particular batch-size. In this work, we present an analysis hinting that high similarity between concurrently processed gradients may be a cause of this performance degradation. We introduce the notion of gradient diversity that measures the dissimilarity between concurrent gradient updates, and show its key role in the performance of mini-batch SGD. We prove that on problems with high gradient diversity, mini-batch SGD is amenable to better speedups, while maintaining the generalization performance of serial (one sample) SGD. We further establish lower bounds on convergence where mini-batch SGD slows down beyond a particular batch-size, solely due to the lack of gradient diversity. We provide experimental evidence indicating the key role of gradient diversity in distributed learning, and discuss how heuristics like dropout, Langevin dynamics, and quantization can improve it.

References in corpus (18)

• TensorFlow: Large-Scale Machine Learning on Heterogeneous Distributed Systems
• Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour
• MXNet: A Flexible and Efficient Machine Learning Library for Heterogeneous Distributed Systems
• HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
• Revisiting Distributed Synchronous SGD
• On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima
• Optimal Distributed Online Prediction using Mini-Batches
• Communication Efficient Distributed Optimization using an Approximate Newton-type Method
• Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting
• Adding Gradient Noise Improves Learning for Very Deep Networks
• An Asynchronous Parallel Stochastic Coordinate Descent Algorithm
• Mini-Batch Primal and Dual Methods for SVMs
• Algorithmic stability and hypothesis complexity
• Distributed Stochastic Variance Reduced Gradient Methods and A Lower Bound for Communication Complexity
• Distributed Mini-Batch SDCA
• NOMAD: Non-locking, stOchastic Multi-machine algorithm for Asynchronous and Decentralized matrix completion
• Determinantal Point Processes for Mini-Batch Diversification
• Constant Step Size Least-Mean-Square: Bias-Variance Trade-offs and Optimal Sampling Distributions

Cited by in corpus (8)

• An Empirical Model of Large-Batch Training
• The Impact of Neural Network Overparameterization on Gradient Confusion and Stochastic Gradient Descent
• Slow and Stale Gradients Can Win the Race: Error-Runtime Trade-offs in Distributed SGD
• Generalization Error Bounds with Probabilistic Guarantee for SGD in Nonconvex Optimization
• Active Mini-Batch Sampling using Repulsive Point Processes
• Robust Learning Rate Selection for Stochastic Optimization via Splitting Diagnostic
• Extrapolation for Large-batch Training in Deep Learning
• Adaptive Discriminative Regularization for Visual Classification