Asynchronous Decentralized Successive Convex Approximation
arXiv:1909.10144
Abstract
We study decentralized asynchronous multiagent optimization over networks, modeled as static (possibly directed) graphs. The optimization problem consists of minimizing a (possibly nonconvex) smooth function--the sum of the agents' local costs--plus a convex (possibly nonsmooth) regularizer, subject to convex constraints. Agents can perform their local computations as well as communicate with their immediate neighbors at any time, without any form of coordination or centralized scheduling; furthermore, when solving their local subproblems, they can use outdated information from their neighbors. We propose the first distributed asynchronous algorithm, termed ASY-DSCA, that converges at an R-linear rate to the optimal solution of convex problems whose objective function satisfies a general error bound condition; this condition is weaker than the more frequently used strong convexity, and it is satisfied by several empirical risk functions that are not strongly convex; examples include LASSO and logistic regression problems. When the objective function is nonconvex, ASY-DSCA converges to a stationary solution of the problem at a sublinear rate.
References in corpus (12)
- A note on the group lasso and a sparse group lasso
- Parallel and Distributed Methods for Nonconvex Optimization--Part II: Applications
- Fully Decentralized Multi-Agent Reinforcement Learning with Networked Agents
- ARock: an Algorithmic Framework for Asynchronous Parallel Coordinate Updates
- Parallel Selective Algorithms for Big Data Optimization
- Decentralized Quasi-Newton Methods
- Asynchronous Accelerated Proximal Stochastic Gradient for Strongly Convex Distributed Finite Sums
- Achieving Linear Convergence in Distributed Asynchronous Multi-agent Optimization
- Accelerated Decentralized Optimization with Local Updates for Smooth and Strongly Convex Objectives
- Asynchronous Parallel Algorithms for Nonconvex Big-Data Optimization. Part II: Complexity and Numerical Results
- Newton-Raphson Consensus under asynchronous and lossy communications for peer-to-peer networks
- Robustness and Tractability for Non-convex M-estimators