A Linearly Convergent Proximal Gradient Algorithm for Decentralized Optimization
arXiv:1905.07996
Abstract
Decentralized optimization is a powerful paradigm that finds applications in engineering and learning design. This work studies decentralized composite optimization problems with non-smooth regularization terms. Most existing gradient-based proximal decentralized methods are known to converge to the optimal solution with sublinear rates, and it remains unclear whether this family of methods can achieve global linear convergence. To tackle this problem, this work assumes the non-smooth regularization term is common across all networked agents, which is the case for many machine learning problems. Under this condition, we design a proximal gradient decentralized algorithm whose fixed point coincides with the desired minimizer. We then provide a concise proof that establishes its linear convergence. In the absence of the non-smooth term, our analysis technique covers the well known EXTRA algorithm and provides useful bounds on the convergence rate and step-size.
arXiv commentNeurIPS 2019
References in corpus (9)
- On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
- Multi-Agent Distributed Optimization via Inexact Consensus ADMM
- Communication Efficient Distributed Optimization using an Approximate Newton-type Method
- ARock: an Algorithmic Framework for Asynchronous Parallel Coordinate Updates
- A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates
- Optimal algorithms for smooth and strongly convex distributed optimization in networks
- Distributed Pareto Optimization via Diffusion Strategies
- COLA: Decentralized Linear Learning
- Distributed soft thresholding for sparse signal recovery
Cited by in corpus (10)
- Variance-Reduced Decentralized Stochastic Optimization with Accelerated Convergence
- Distributed Algorithms for Composite Optimization: Unified Framework and Convergence Analysis
- A Unified and Refined Convergence Analysis for Non-Convex Decentralized Learning
- An introduction to decentralized stochastic optimization with gradient tracking
- Gradient tracking and variance reduction for decentralized optimization and machine learning
- PMGT-VR: A decentralized proximal-gradient algorithmic framework with variance reduction
- NPGA: A Unified Algorithmic Framework for Decentralized Constraint-Coupled Optimization
- A Unified Contraction Analysis of a Class of Distributed Algorithms for Composite Optimization
- On linear convergence of two decentralized algorithms
- Decentralized Composite Optimization in Stochastic Networks: A Dual Averaging Approach with Linear Convergence