Distributed Fixed Point Methods with Compressed Iterates

Abstract

We propose basic and natural assumptions under which iterative optimization methods with compressed iterates can be analyzed. This problem is motivated by the practice of federated learning, where a large model stored in the cloud is compressed before it is sent to a mobile device, which then proceeds with training based on local data. We develop standard and variance reduced methods, and establish communication complexity bounds. Our algorithms are the first distributed methods with compressed iterates, and the first fixed point methods with compressed iterates.

15 pages, 4 algorithms, 4 Theorems

References in corpus (13)

• Federated Learning: Strategies for Improving Communication Efficiency
• FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantization
• Sparsified SGD with Memory
• Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication
• Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms
• Expanding the Reach of Federated Learning by Reducing Client Resource Requirements
• Distributed Learning with Compressed Gradient Differences
• Stochastic Distributed Learning with Gradient Quantization and Variance Reduction
• Natural Compression for Distributed Deep Learning
• On perturbed proximal gradient algorithms
• SGD: General Analysis and Improved Rates
• Gradient Descent with Compressed Iterates
• Nested Distributed Gradient Methods with Adaptive Quantized Communication

Cited by in corpus (3)

• A Unified Analysis of Stochastic Gradient Methods for Nonconvex Federated Optimization
• From Local SGD to Local Fixed-Point Methods for Federated Learning
• Local Methods with Adaptivity via Scaling