Faster Non-Convex Federated Learning via Global and Local Momentum

Abstract

We propose \texttt{FedGLOMO}, a novel federated learning (FL) algorithm with an iteration complexity of $\mathcal{O}({\epsilon }^{-1.5})$ to converge to an $\epsilon$-stationary point (i.e., $\mathbb{E}[\Vert \nabla f(\mathbf{x}){\Vert }^2]\le \epsilon$) for smooth non-convex functions -- under arbitrary client heterogeneity and compressed communication -- compared to the $\mathcal{O}({\epsilon }^{-2})$ complexity of most prior works. Our key algorithmic idea that enables achieving this improved complexity is based on the observation that the convergence in FL is hampered by two sources of high variance: (i) the global server aggregation step with multiple local updates, exacerbated by client heterogeneity, and (ii) the noise of the local client-level stochastic gradients. By modeling the server aggregation step as a generalized gradient-type update, we propose a variance-reducing momentum-based global update at the server, which when applied in conjunction with variance-reduced local updates at the clients, enables \texttt{FedGLOMO} to enjoy an improved convergence rate. Moreover, we derive our results under a novel and more realistic client-heterogeneity assumption which we verify empirically -- unlike prior assumptions that are hard to verify. Our experiments illustrate the intrinsic variance reduction effect of \texttt{FedGLOMO}, which implicitly suppresses client-drift in heterogeneous data distribution settings and promotes communication efficiency.

References in corpus (32)

• Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms
• Communication-Efficient Learning of Deep Networks from Decentralized Data
• Federated Learning: Strategies for Improving Communication Efficiency
• Federated Optimization: Distributed Machine Learning for On-Device Intelligence
• Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training
• On the Convergence of FedAvg on Non-IID Data
• QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
• SCAFFOLD: Stochastic Controlled Averaging for Federated Learning
• Federated Optimization in Heterogeneous Networks
• FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantization
• SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
• Sparsified SGD with Memory
• Local SGD Converges Fast and Communicates Little
• Communication Compression for Decentralized Training
• A Unified Theory of Decentralized SGD with Changing Topology and Local Updates
• Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms
• Distributed Mean Estimation with Limited Communication
• Adaptive Federated Optimization
• Mime: Mimicking Centralized Stochastic Algorithms in Federated Learning
• Variance Reduced Local SGD with Lower Communication Complexity
• Stochastic Distributed Learning with Gradient Quantization and Variance Reduction
• The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication
• SlowMo: Improving Communication-Efficient Distributed SGD with Slow Momentum
• On exponential convergence of SGD in non-convex over-parametrized learning
• Is Local SGD Better than Minibatch SGD?
• Faster On-Device Training Using New Federated Momentum Algorithm
• Error Compensated Quantized SGD and its Applications to Large-scale Distributed Optimization
• Federated Learning with Compression: Unified Analysis and Sharp Guarantees
• Communication trade-offs for synchronized distributed SGD with large step size
• An Optimal Hybrid Variance-Reduced Algorithm for Stochastic Composite Nonconvex Optimization
• On the Benefits of Multiple Gossip Steps in Communication-Constrained Decentralized Optimization
• Decentralized Optimization On Time-Varying Directed Graphs Under Communication Constraints

Cited by in corpus (6)

• Quasi-Global Momentum: Accelerating Decentralized Deep Learning on Heterogeneous Data
• STEM: A Stochastic Two-Sided Momentum Algorithm Achieving Near-Optimal Sample and Communication Complexities for Federated Learning
• MARINA: Faster Non-Convex Distributed Learning with Compression
• Bias-Variance Reduced Local SGD for Less Heterogeneous Federated Learning
• Robust Training in High Dimensions via Block Coordinate Geometric Median Descent
• Improved Convergence Analysis and SNR Control Strategies for Federated Learning in the Presence of Noise