DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compression

Abstract

A standard approach in large scale machine learning is distributed stochastic gradient training, which requires the computation of aggregated stochastic gradients over multiple nodes on a network. Communication is a major bottleneck in such applications, and in recent years, compressed stochastic gradient methods such as QSGD (quantized SGD) and sparse SGD have been proposed to reduce communication. It was also shown that error compensation can be combined with compression to achieve better convergence in a scheme that each node compresses its local stochastic gradient and broadcast the result to all other nodes over the network in a single pass. However, such a single pass broadcast approach is not realistic in many practical implementations. For example, under the popular parameter server model for distributed learning, the worker nodes need to send the compressed local gradients to the parameter server, which performs the aggregation. The parameter server has to compress the aggregated stochastic gradient again before sending it back to the worker nodes. In this work, we provide a detailed analysis on this two-pass communication model and its asynchronous parallel variant, with error-compensated compression both on the worker nodes and on the parameter server. We show that the error-compensated stochastic gradient algorithm admits three very nice properties: 1) it is compatible with an \emph{arbitrary} compression technique; 2) it admits an improved convergence rate than the non error-compensated stochastic gradient methods such as QSGD and sparse SGD; 3) it admits linear speedup with respect to the number of workers. The empirical study is also conducted to validate our theoretical results.

Cited by in corpus (51)

• A Field Guide to Federated Optimization
• Database Meets Deep Learning: Challenges and Opportunities
• Variance Reduced Local SGD with Lower Communication Complexity
• Joint Optimization of Communications and Federated Learning Over the Air
• Communication-Efficient Distributed Blockwise Momentum SGD with Error-Feedback
• Understanding Top-k Sparsification in Distributed Deep Learning
• The Internet of Federated Things (IoFT): A Vision for the Future and In-depth Survey of Data-driven Approaches for Federated Learning
• EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback
• Optimal Gradient Compression for Distributed and Federated Learning
• Moniqua: Modulo Quantized Communication in Decentralized SGD
• Hyper-Sphere Quantization: Communication-Efficient SGD for Federated Learning
• Federated Learning With Quantized Global Model Updates
• A Double Residual Compression Algorithm for Efficient Distributed Learning
• Compressed Gradient Tracking for Decentralized Optimization Over General Directed Networks
• $\text{DeepSqueeze}$: Decentralization Meets Error-Compensated Compression
• On the Utility of Gradient Compression in Distributed Training Systems
• BROADCAST: Reducing Both Stochastic and Compression Noise to Robustify Communication-Efficient Federated Learning
• 1-bit Adam: Communication Efficient Large-Scale Training with Adam's Convergence Speed
• Taming Momentum in a Distributed Asynchronous Environment
• ProgFed: Effective, Communication, and Computation Efficient Federated Learning by Progressive Training
• Linear Convergent Decentralized Optimization with Compression
• BlueFog: Make Decentralized Algorithms Practical for Optimization and Deep Learning
• Distributed Second Order Methods with Fast Rates and Compressed Communication
• Efficient Sparse Secure Aggregation for Federated Learning
• Stochastic Sign Descent Methods: New Algorithms and Better Theory
• Bidirectional compression in heterogeneous settings for distributed or federated learning with partial participation: tight convergence guarantees
• Distributed Optimization over Block-Cyclic Data
• Error Compensated Distributed SGD Can Be Accelerated
• PowerGossip: Practical Low-Rank Communication Compression in Decentralized Deep Learning
• Communication-Efficient Distributed SGD with Error-Feedback, Revisited
• Improved Convergence Analysis and SNR Control Strategies for Federated Learning in the Presence of Noise
• On the Convergence of Decentralized Adaptive Gradient Methods
• Pufferfish: Communication-efficient Models At No Extra Cost
• On the Benefits of Multiple Gossip Steps in Communication-Constrained Decentralized Optimization
• APMSqueeze: A Communication Efficient Adam-Preconditioned Momentum SGD Algorithm
• Trends and Advancements in Deep Neural Network Communication
• Decentralized Composite Optimization with Compression
• Accelerating Gossip SGD with Periodic Global Averaging
• Cross-Gradient Aggregation for Decentralized Learning from Non-IID data
• Optimal Complexity in Decentralized Training
• ErrorCompensatedX: error compensation for variance reduced algorithms
• Permutation Compressors for Provably Faster Distributed Nonconvex Optimization
• Smoothness Matrices Beat Smoothness Constants: Better Communication Compression Techniques for Distributed Optimization
• Accelerated Sparsified SGD with Error Feedback
• On the Convergence of Quantized Parallel Restarted SGD for Central Server Free Distributed Training
• DEED: A General Quantization Scheme for Communication Efficiency in Bits
• Error Compensated Loopless SVRG, Quartz, and SDCA for Distributed Optimization
• Communication-Compressed Adaptive Gradient Method for Distributed Nonconvex Optimization
• Federated Submodel Optimization for Hot and Cold Data Features
• Decentralized Wireless Federated Learning with Differential Privacy
• MURANA: A Generic Framework for Stochastic Variance-Reduced Optimization