Stochastic Distributed Learning with Gradient Quantization and Variance Reduction

Abstract

We consider distributed optimization where the objective function is spread among different devices, each sending incremental model updates to a central server. To alleviate the communication bottleneck, recent work proposed various schemes to compress (e.g.\ quantize or sparsify) the gradients, thereby introducing additional variance $\omega \ge 1$ that might slow down convergence. For strongly convex functions with condition number $\kappa$ distributed among $n$ machines, we (i) give a scheme that converges in $\mathcal{O}((\kappa +\kappa \frac{\omega }{n}+\omega )$ $\log (1/\epsilon ))$ steps to a neighborhood of the optimal solution. For objective functions with a finite-sum structure, each worker having less than $m$ components, we (ii) present novel variance reduced schemes that converge in $\mathcal{O}((\kappa +\kappa \frac{\omega }{n}+\omega +m)\log (1/\epsilon ))$ steps to arbitrary accuracy $\epsilon >0$. These are the first methods that achieve linear convergence for arbitrary quantized updates. We also (iii) give analysis for the weakly convex and non-convex cases and (iv) verify in experiments that our novel variance reduced schemes are more efficient than the baselines.

10 pages, 24 pages of Appendix

References in corpus (22)

• Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour
• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• Optimal Distributed Online Prediction using Mini-Batches
• Communication Efficient Distributed Optimization using an Approximate Newton-type Method
• Sparsified SGD with Memory
• Local SGD Converges Fast and Communicates Little
• Distributed Coordinate Descent Method for Learning with Big Data
• Communication Compression for Decentralized Training
• Distributed Mean Estimation with Limited Communication
• AIDE: Fast and Communication Efficient Distributed Optimization
• Distributed Learning with Compressed Gradient Differences
• Adding vs. Averaging in Distributed Primal-Dual Optimization
• ImageNet Training in Minutes
• SDNA: Stochastic Dual Newton Ascent for Empirical Risk Minimization
• Distributed learning with compressed gradients
• Error Compensated Quantized SGD and its Applications to Large-scale Distributed Optimization
• SDCA without Duality, Regularization, and Individual Convexity
• Stochastic Dual Coordinate Ascent with Adaptive Probabilities
• Primal Method for ERM with Flexible Mini-batching Schemes and Non-convex Losses
• Randomized Distributed Mean Estimation: Accuracy vs Communication
• 99% of Distributed Optimization is a Waste of Time: The Issue and How to Fix it

Cited by in corpus (49)

• UVeQFed: Universal Vector Quantization for Federated Learning
• A Field Guide to Federated Optimization
• Natural Compression for Distributed Deep Learning
• Acceleration for Compressed Gradient Descent in Distributed and Federated Optimization
• Better Theory for SGD in the Nonconvex World
• Near-Optimal Sparse Allreduce for Distributed Deep Learning
• On Biased Compression for Distributed Learning
• Towards Communication-efficient and Attack-Resistant Federated Edge Learning for Industrial Internet of Things
• EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback
• Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradients
• Optimal Gradient Compression for Distributed and Federated Learning
• Linearly Converging Error Compensated SGD
• Decentralized Deep Learning with Arbitrary Communication Compression
• A Double Residual Compression Algorithm for Efficient Distributed Learning
• Federated Learning with Compression: Unified Analysis and Sharp Guarantees
• Communication-Efficient Local Decentralized SGD Methods
• Recent theoretical advances in decentralized distributed convex optimization
• A Unified Analysis of Stochastic Gradient Methods for Nonconvex Federated Optimization
• A Better Alternative to Error Feedback for Communication-Efficient Distributed Learning
• A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descent
• Bayesian Federated Learning over Wireless Networks
• MARINA: Faster Non-Convex Distributed Learning with Compression
• FedNL: Making Newton-Type Methods Applicable to Federated Learning
• Gradient Descent with Compressed Iterates
• FedSKETCH: Communication-Efficient and Private Federated Learning via Sketching
• Distributed Second Order Methods with Fast Rates and Compressed Communication
• Faster Non-Convex Federated Learning via Global and Local Momentum
• Local SGD: Unified Theory and New Efficient Methods
• On Communication Compression for Distributed Optimization on Heterogeneous Data
• Uncertainty Principle for Communication Compression in Distributed and Federated Learning and the Search for an Optimal Compressor
• Error Compensated Distributed SGD Can Be Accelerated
• Bidirectional compression in heterogeneous settings for distributed or federated learning with partial participation: tight convergence guarantees
• MISO is Making a Comeback With Better Proofs and Rates
• CANITA: Faster Rates for Distributed Convex Optimization with Communication Compression
• DeepReduce: A Sparse-tensor Communication Framework for Distributed Deep Learning
• Distributed Fixed Point Methods with Compressed Iterates
• Data-Importance Aware User Scheduling for Communication-Efficient Edge Machine Learning
• Leveraging Spatial and Temporal Correlations in Sparsified Mean Estimation
• A Linearly Convergent Algorithm for Decentralized Optimization: Sending Less Bits for Free!
• Moshpit SGD: Communication-Efficient Decentralized Training on Heterogeneous Unreliable Devices
• QLSD: Quantised Langevin stochastic dynamics for Bayesian federated learning
• Theoretically Better and Numerically Faster Distributed Optimization with Smoothness-Aware Quantization Techniques
• ErrorCompensatedX: error compensation for variance reduced algorithms
• Smoothness Matrices Beat Smoothness Constants: Better Communication Compression Techniques for Distributed Optimization
• Basis Matters: Better Communication-Efficient Second Order Methods for Federated Learning
• CADA: Communication-Adaptive Distributed Adam
• Error Compensated Loopless SVRG, Quartz, and SDCA for Distributed Optimization
• MURANA: A Generic Framework for Stochastic Variance-Reduced Optimization
• Optimization for Supervised Machine Learning: Randomized Algorithms for Data and Parameters