A general framework for decentralized optimization with first-order methods

Abstract

Decentralized optimization to minimize a finite sum of functions over a network of nodes has been a significant focus within control and signal processing research due to its natural relevance to optimal control and signal estimation problems. More recently, the emergence of sophisticated computing and large-scale data science needs have led to a resurgence of activity in this area. In this article, we discuss decentralized first-order gradient methods, which have found tremendous success in control, signal processing, and machine learning problems, where such methods, due to their simplicity, serve as the first method of choice for many complex inference and training tasks. In particular, we provide a general framework of decentralized first-order methods that is applicable to undirected and directed communication networks alike, and show that much of the existing work on optimization and consensus can be related explicitly to this framework. We further extend the discussion to decentralized stochastic first-order methods that rely on stochastic gradients at each node and describe how local variance reduction schemes, previously shown to have promise in the centralized settings, are able to improve the performance of decentralized methods when combined with what is known as gradient tracking. We motivate and demonstrate the effectiveness of the corresponding methods in the context of machine learning and signal processing problems that arise in decentralized environments.

References in corpus (26)

• On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
• Diffusion Adaptation Strategies for Distributed Optimization and Learning over Networks
• Distributing the Kalman Filter for Large-Scale Systems
• Communication Efficient Distributed Optimization using an Approximate Newton-type Method
• D-ADMM: A Communication-Efficient Distributed Algorithm For Separable Optimization
• A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates
• Distributed Basis Pursuit
• Optimal algorithms for smooth and strongly convex distributed optimization in networks
• Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication
• D${}^2$: Decentralized Training over Decentralized Data
• DSA: Decentralized Double Stochastic Averaging Gradient Algorithm
• An Exact Quantized Decentralized Gradient Descent Algorithm
• Stochastic Gradient Push for Distributed Deep Learning
• Decentralized Quasi-Newton Methods
• Variance-Reduced Decentralized Stochastic Optimization with Accelerated Convergence
• An improved convergence analysis for decentralized online stochastic non-convex optimization
• Distributed Non-Convex First-Order Optimization and Information Processing: Lower Complexity Bounds and Rate Optimal Algorithms
• On the Influence of Bias-Correction on Distributed Stochastic Optimization
• Convergence Rates of Distributed Nesterov-like Gradient Methods on Random Networks
• A Sharp Estimate on the Transient Time of Distributed Stochastic Gradient Descent
• Robust Asynchronous Stochastic Gradient-Push: Asymptotically Optimal and Network-Independent Performance for Strongly Convex Functions
• A System Theoretical Perspective to Gradient-Tracking Algorithms for Distributed Quadratic Optimization
• Asynchronous Accelerated Proximal Stochastic Gradient for Strongly Convex Distributed Finite Sums
• Improving the Sample and Communication Complexity for Decentralized Non-Convex Optimization: A Joint Gradient Estimation and Tracking Approach
• Variance-Reduced Stochastic Learning under Random Reshuffling
• Fast decentralized non-convex finite-sum optimization with recursive variance reduction