Parallel Restarted SPIDER -- Communication Efficient Distributed Nonconvex Optimization with Optimal Computation Complexity

Abstract

In this paper, we propose a distributed algorithm for stochastic smooth, non-convex optimization. We assume a worker-server architecture where $N$ nodes, each having $n$ (potentially infinite) number of samples, collaborate with the help of a central server to perform the optimization task. The global objective is to minimize the average of local cost functions available at individual nodes. The proposed approach is a non-trivial extension of the popular parallel-restarted SGD algorithm, incorporating the optimal variance-reduction based SPIDER gradient estimator into it. We prove convergence of our algorithm to a first-order stationary solution. The proposed approach achieves the best known communication complexity $O({\epsilon }^{-1})$ along with the optimal computation complexity. For finite-sum problems (finite $n$), we achieve the optimal computation (IFO) complexity $O(\sqrt{Nn}{\epsilon }^{-1})$. For online problems ($n$ unknown or infinite), we achieve the optimal IFO complexity $O({\epsilon }^{-3/2})$. In both the cases, we maintain the linear speedup achieved by existing methods. This is a massive improvement over the $O({\epsilon }^{-2})$ IFO complexity of the existing approaches. Additionally, our algorithm is general enough to allow non-identical distributions of data across workers, as in the recently proposed federated learning paradigm.

References in corpus (16)

• Federated Optimization: Distributed Machine Learning for On-Device Intelligence
• QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
• TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learning
• Communication Efficient Distributed Optimization using an Approximate Newton-type Method
• SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
• Don't Use Large Mini-Batches, Use Local SGD
• Local SGD Converges Fast and Communicates Little
• On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization
• AIDE: Fast and Communication Efficient Distributed Optimization
• Parallel SGD: When does averaging help?
• Stochastic Recursive Gradient Algorithm for Nonconvex Optimization
• On the Computation and Communication Complexity of Parallel SGD with Dynamic Batch Sizes for Stochastic Non-Convex Optimization
• SpiderBoost and Momentum: Faster Stochastic Variance Reduction Algorithms
• Convergence of Distributed Stochastic Variance Reduced Methods without Sampling Extra Data
• Less than a Single Pass: Stochastically Controlled Stochastic Gradient Method
• Improving the Sample and Communication Complexity for Decentralized Non-Convex Optimization: A Joint Gradient Estimation and Tracking Approach

Cited by in corpus (8)

• FedCluster: Boosting the Convergence of Federated Learning via Cluster-Cycling
• Tighter Theory for Local SGD on Identical and 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
• Distributed Stochastic Non-Convex Optimization: Momentum-Based Variance Reduction
• Local Methods with Adaptivity via Scaling
• Local SGD for Near-Quadratic Problems: Improving Convergence under Unconstrained Noise Conditions