ErrorCompensatedX: error compensation for variance reduced algorithms
arXiv:2108.02102
Abstract
Communication cost is one major bottleneck for the scalability for distributed learning. One approach to reduce the communication cost is to compress the gradient during communication. However, directly compressing the gradient decelerates the convergence speed, and the resulting algorithm may diverge for biased compression. Recent work addressed this problem for stochastic gradient descent by adding back the compression error from the previous step. This idea was further extended to one class of variance reduced algorithms, where the variance of the stochastic gradient is reduced by taking a moving average over all history gradients. However, our analysis shows that just adding the previous step's compression error, as done in existing work, does not fully compensate the compression error. So, we propose ErrorCompensatedX, which uses the compression error from the previous two steps. We show that ErrorCompensatedX can achieve the same asymptotic convergence rate with the training without compression. Moreover, we provide a unified theoretical analysis framework for this class of variance reduced algorithms, with or without error compensation.
References in corpus (17)
- SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
- QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
- Sparsified SGD with Memory
- DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compression
- Distributed Learning with Compressed Gradient Differences
- Stochastic Distributed Learning with Gradient Quantization and Variance Reduction
- Communication-Efficient Distributed Learning via Lazily Aggregated Quantized Gradients
- Error Compensated Quantized SGD and its Applications to Large-scale Distributed Optimization
- Linearly Converging Error Compensated SGD
- Double Quantization for Communication-Efficient Distributed Optimization
- Stochastic Recursive Momentum for Policy Gradient Methods
- ScaleCom: Scalable Sparsified Gradient Compression for Communication-Efficient Distributed Training
- Reducing the variance in online optimization by transporting past gradients
- PowerGossip: Practical Low-Rank Communication Compression in Decentralized Deep Learning
- Accelerated Stochastic Gradient-free and Projection-free Methods
- CSER: Communication-efficient SGD with Error Reset
- On the Convergence of Memory-Based Distributed SGD