A Provably Communication-Efficient Asynchronous Distributed Inference Method for Convex and Nonconvex Problems

Abstract

This paper proposes and analyzes a communication-efficient distributed optimization framework for general nonconvex nonsmooth signal processing and machine learning problems under an asynchronous protocol. At each iteration, worker machines compute gradients of a known empirical loss function using their own local data, and a master machine solves a related minimization problem to update the current estimate. We prove that for nonconvex nonsmooth problems, the proposed algorithm converges with a sublinear rate over the number of communication rounds, coinciding with the best theoretical rate that can be achieved for this class of problems. Linear convergence is established without any statistical assumptions of the local data for problems characterized by composite loss functions whose smooth parts are strongly convex. Extensive numerical experiments verify that the performance of the proposed approach indeed improves -- sometimes significantly -- over other state-of-the-art algorithms in terms of total communication efficiency.

arXiv comment15 pages, 9 figures, preliminary version appeared in the proceedings of the 2018 IEEE Global Conference on Signal and Information Processing (GlobalSIP 2018)

References in corpus (21)

• HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
• Harnessing Smoothness to Accelerate Distributed Optimization
• Optimal Distributed Online Prediction using Mini-Batches
• Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent
• Communication Efficient Distributed Optimization using an Approximate Newton-type Method
• Decomposition by Partial Linearization: Parallel Optimization of Multi-Agent Systems
• Parallel and Distributed Methods for Nonconvex Optimization--Part II: Applications
• Asynchronous Distributed ADMM for Large-Scale Optimization- Part I: Algorithm and Convergence Analysis
• Parallel Coordinate Descent for L1-Regularized Loss Minimization
• Regularization Techniques for Learning with Matrices
• Communication Complexity of Distributed Convex Learning and Optimization
• Communication-Efficient Distributed Dual Coordinate Ascent
• Adaptive Graph Signal Processing: Algorithms and Optimal Sampling Strategies
• A Unified Successive Pseudo-Convex Approximation Framework
• A Distributed Tracking Algorithm for Reconstruction of Graph Signals
• Asynchronous Distributed ADMM for Large-Scale Optimization- Part II: Linear Convergence Analysis and Numerical Performance
• Efficient Distributed Learning with Sparsity
• Distributed Stochastic Variance Reduced Gradient Methods and A Lower Bound for Communication Complexity
• A Distributed, Asynchronous and Incremental Algorithm for Nonconvex Optimization: An ADMM Based Approach
• Analysis and Implementation of an Asynchronous Optimization Algorithm for the Parameter Server
• A Distributed One-Step Estimator