A Unified Analysis of Stochastic Gradient Methods for Nonconvex Federated Optimization

Abstract

In this paper, we study the performance of a large family of SGD variants in the smooth nonconvex regime. To this end, we propose a generic and flexible assumption capable of accurate modeling of the second moment of the stochastic gradient. Our assumption is satisfied by a large number of specific variants of SGD in the literature, including SGD with arbitrary sampling, SGD with compressed gradients, and a wide variety of variance-reduced SGD methods such as SVRG and SAGA. We provide a single convergence analysis for all methods that satisfy the proposed unified assumption, thereby offering a unified understanding of SGD variants in the nonconvex regime instead of relying on dedicated analyses of each variant. Moreover, our unified analysis is accurate enough to recover or improve upon the best-known convergence results of several classical methods, and also gives new convergence results for many new methods which arise as special cases. In the more general distributed/federated nonconvex optimization setup, we propose two new general algorithmic frameworks differing in whether direct gradient compression (DC) or compression of gradient differences (DIANA) is used. We show that all methods captured by these two frameworks also satisfy our unified assumption. Thus, our unified convergence analysis also captures a large variety of distributed methods utilizing compressed communication. Finally, we also provide a unified analysis for obtaining faster linear convergence rates in this nonconvex regime under the PL condition.

arXiv comment77 pages

References in corpus (25)

• Communication-Efficient Learning of Deep Networks from Decentralized Data
• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• SCAFFOLD: Stochastic Controlled Averaging for Federated Learning
• TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learning
• Federated Optimization in Heterogeneous Networks
• Stochastic Variance Reduction for Nonconvex Optimization
• Local SGD Converges Fast and Communicates Little
• Distributed Learning with Compressed Gradient Differences
• Stochastic Distributed Learning with Gradient Quantization and Variance Reduction
• Acceleration for Compressed Gradient Descent in Distributed and Federated Optimization
• First Analysis of Local GD on Heterogeneous Data
• Natural Compression for Distributed Deep Learning
• Stochastic Nested Variance Reduction for Nonconvex Optimization
• Better Theory for SGD in the Nonconvex World
• ProxSARAH: An Efficient Algorithmic Framework for Stochastic Composite Nonconvex Optimization
• Distributed learning with compressed gradients
• SEGA: Variance Reduction via Gradient Sketching
• An optimal randomized incremental gradient method
• Communication-Efficient Local Decentralized SGD Methods
• Variance Reduced Stochastic Gradient Descent with Neighbors
• A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descent
• Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loop
• L-SVRG and L-Katyusha with Arbitrary Sampling
• Stabilized SVRG: Simple Variance Reduction for Nonconvex Optimization
• Distributed Fixed Point Methods with Compressed Iterates

Cited by in corpus (13)

• Federated Learning Based on Dynamic Regularization
• Acceleration for Compressed Gradient Descent in Distributed and Federated Optimization
• EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback
• PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization
• MARINA: Faster Non-Convex Distributed Learning with Compression
• ZeroSARAH: Efficient Nonconvex Finite-Sum Optimization with Zero Full Gradient Computation
• Minimax Estimation for Personalized Federated Learning: An Alternative between FedAvg and Local Training?
• FedPAGE: A Fast Local Stochastic Gradient Method for Communication-Efficient Federated Learning
• ANITA: An Optimal Loopless Accelerated Variance-Reduced Gradient Method
• CANITA: Faster Rates for Distributed Convex Optimization with Communication Compression
• Moshpit SGD: Communication-Efficient Decentralized Training on Heterogeneous Unreliable Devices
• Communication-Efficient Agnostic Federated Averaging
• FLIX: A Simple and Communication-Efficient Alternative to Local Methods in Federated Learning