The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication

Abstract

We analyze (stochastic) gradient descent (SGD) with delayed updates on smooth quasi-convex and non-convex functions and derive concise, non-asymptotic, convergence rates. We show that the rate of convergence in all cases consists of two terms: (i) a stochastic term which is not affected by the delay, and (ii) a higher order deterministic term which is only linearly slowed down by the delay. Thus, in the presence of noise, the effects of the delay become negligible after a few iterations and the algorithm converges at the same optimal rate as standard SGD. This result extends a line of research that showed similar results in the asymptotic regime or for strongly-convex quadratic functions only. We further show similar results for SGD with more intricate form of delayed gradients -- compressed gradients under error compensation and for local~SGD where multiple workers perform local steps before communicating with each other. In all of these settings, we improve upon the best known rates. These results show that SGD is robust to compressed and/or delayed stochastic gradient updates. This is in particular important for distributed parallel implementations, where asynchronous and communication efficient methods are the key to achieve linear speedups for optimization with multiple devices.

Submitted 9/19, Published 9/20

References in corpus (6)

• A Unified Theory of Decentralized SGD with Changing Topology and Local Updates
• Error Feedback Fixes SignSGD and other Gradient Compression Schemes
• Parallel SGD: When does averaging help?
• Communication trade-offs for synchronized distributed SGD with large step size
• The Complexity of Making the Gradient Small in Stochastic Convex Optimization
• On Communication Compression for Distributed Optimization on Heterogeneous Data

Cited by in corpus (60)

• SCAFFOLD: Stochastic Controlled Averaging for Federated Learning
• Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization
• A Field Guide to Federated Optimization
• A Unified Theory of Decentralized SGD with Changing Topology and Local Updates
• Adaptive Federated Optimization
• Optimal Client Sampling for Federated Learning
• Mime: Mimicking Centralized Stochastic Algorithms in Federated Learning
• Dynamic Model Pruning with Feedback
• Client Selection in Federated Learning: Convergence Analysis and Power-of-Choice Selection Strategies
• Better Theory for SGD in the Nonconvex World
• On Biased Compression for Distributed Learning
• Is Local SGD Better than Minibatch SGD?
• EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback
• Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradients
• Tighter Theory for Local SGD on Identical and Heterogeneous Data
• Optimal Gradient Compression for Distributed and Federated Learning
• Federated Learning with Compression: Unified Analysis and Sharp Guarantees
• Consensus Control for Decentralized Deep Learning
• Federated Accelerated Stochastic Gradient Descent
• On the Outsized Importance of Learning Rates in Local Update Methods
• A Better Alternative to Error Feedback for Communication-Efficient Distributed Learning
• Rethinking gradient sparsification as total error minimization
• Stragglers Are Not Disaster: A Hybrid Federated Learning Algorithm with Delayed Gradients
• Achieving Linear Speedup with Partial Worker Participation in Non-IID Federated Learning
• Accordion: Adaptive Gradient Communication via Critical Learning Regime Identification
• Personalized Federated Learning for Heterogeneous Clients with Clustered Knowledge Transfer
• On the Convergence of SGD with Biased Gradients
• ADOM: Accelerated Decentralized Optimization Method for Time-Varying Networks
• rTop-k: A Statistical Estimation Approach to Distributed SGD
• Local SGD With a Communication Overhead Depending Only on the Number of Workers
• Distributed Second Order Methods with Fast Rates and Compressed Communication
• FedSKETCH: Communication-Efficient and Private Federated Learning via Sketching
• Multi-Agent Online Optimization with Delays: Asynchronicity, Adaptivity, and Optimism
• Local SGD: Unified Theory and New Efficient Methods
• On Communication Compression for Distributed Optimization on Heterogeneous Data
• Faster Non-Convex Federated Learning via Global and Local Momentum
• Communication-efficient SGD: From Local SGD to One-Shot Averaging
• Error Compensated Distributed SGD Can Be Accelerated
• PowerGossip: Practical Low-Rank Communication Compression in Decentralized Deep Learning
• Robust Training in High Dimensions via Block Coordinate Geometric Median Descent
• Elastic Consistency: A General Consistency Model for Distributed Stochastic Gradient Descent
• Leveraging Spatial and Temporal Correlations in Sparsified Mean Estimation
• FedSEAL: Semi-Supervised Federated Learning with Self-Ensemble Learning and Negative Learning
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks
• A Linearly Convergent Algorithm for Decentralized Optimization: Sending Less Bits for Free!
• Smoothness Matrices Beat Smoothness Constants: Better Communication Compression Techniques for Distributed Optimization
• Quantized Adam with Error Feedback
• Permutation Compressors for Provably Faster Distributed Nonconvex Optimization
• The Minimax Complexity of Distributed Optimization
• Delayed Projection Techniques for Linearly Constrained Problems: Convergence Rates, Acceleration, and Applications
• Extrapolation for Large-batch Training in Deep Learning
• Federated Submodel Optimization for Hot and Cold Data Features
• Communication-Compressed Adaptive Gradient Method for Distributed Nonconvex Optimization
• Critical Parameters for Scalable Distributed Learning with Large Batches and Asynchronous Updates
• Gaussian Process Inference Using Mini-batch Stochastic Gradient Descent: Convergence Guarantees and Empirical Benefits
• Error Compensated Loopless SVRG, Quartz, and SDCA for Distributed Optimization
• CFedAvg: Achieving Efficient Communication and Fast Convergence in Non-IID Federated Learning
• Sparsification as a Remedy for Staleness in Distributed Asynchronous SGD
• Speeding-Up Back-Propagation in DNN: Approximate Outer Product with Memory
• Communication Efficient Generalized Tensor Factorization for Decentralized Healthcare Networks