Asynchronous Distributed Optimization Via Randomized Dual Proximal Gradient

DOI10.1109/TAC.2016.2607023zbMATH Open1366.90163arXiv1509.08373OpenAlexW2963590077MaRDI QIDQ5280397FDOQ5280397

Authors: Ivano Notarnicola, Giuseppe Notarstefano 

Publication date: 27 July 2017

Published in: IEEE Transactions on Automatic Control (Search for Journal in Brave)

Abstract: In this paper we consider distributed optimization problems in which the cost function is separable, i.e., a sum of possibly non-smooth functions all sharing a common variable, and can be split into a strongly convex term and a convex one. The second term is typically used to encode constraints or to regularize the solution. We propose a class of distributed optimization algorithms based on proximal gradient methods applied to the dual problem. We show that, by choosing suitable primal variable copies, the dual problem is itself separable when written in terms of conjugate functions, and the dual variables can be stacked into non-overlapping blocks associated to the computing nodes. We first show that a weighted proximal gradient on the dual function leads to a synchronous distributed algorithm with local dual proximal gradient updates at each node. Then, as main paper contribution, we develop asynchronous versions of the algorithm in which the node updates are triggered by local timers without any global iteration counter. The algorithms are shown to be proper randomized block-coordinate proximal gradient updates on the dual function.

Full work available at URL: https://arxiv.org/abs/1509.08373

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25) Distributed algorithms (68W15) Derivative-free methods and methods using generalized derivatives (90C56)

Cited In (17)

• An inertial parallel and asynchronous forward-backward iteration for distributed convex optimization
• Composite optimization with coupling constraints via dual proximal gradient method with applications to asynchronous networks
• Distributed constrained stochastic subgradient algorithms based on random projection and asynchronous broadcast over networks
• A distributed asynchronous method of multipliers for constrained nonconvex optimization
• An Asynchronous Mini-Batch Algorithm for Regularized Stochastic Optimization
• Title not available (Why is that?)
• A Coordinate Descent Primal-Dual Algorithm and Application to Distributed Asynchronous Optimization
• Asynchronous Distributed Optimization Over Lossy Networks via Relaxed ADMM: Stability and Linear Convergence
• Asynchronous Distributed ADMM for Large-Scale Optimization—Part II: Linear Convergence Analysis and Numerical Performance
• Decentralized proximal splitting algorithms for composite constrained convex optimization
• A Distributed, Asynchronous, and Incremental Algorithm for Nonconvex Optimization: An ADMM Approach
• An asynchronous subgradient-proximal method for solving additive convex optimization problems
• A distributed proximal gradient method with time-varying delays for solving additive convex optimizations
• Distributed asynchronous incremental subgradient methods
• Distributed deterministic asynchronous algorithms in time-varying graphs through Dykstra splitting
• Distributed composite optimization for multi-agent systems with asynchrony
• An Optimal Algorithm for Decentralized Finite-Sum Optimization

This page was built for publication: Asynchronous Distributed Optimization Via Randomized Dual Proximal Gradient

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5280397)