An Asynchronous Distributed Proximal Gradient Method for Composite Convex Optimization

MaRDI QIDQ6255080zbMATH OpenFDO

Authors N. S. Aybat, G. Iyengar, Zi Wang

Publication date 30 September 2014

Abstract: We propose a distributed first-order augmented Lagrangian (DFAL) algorithm to minimize the sum of composite convex functions, where each term in the sum is a private cost function belonging to a node, and only nodes connected by an edge can directly communicate with each other. This optimization model abstracts a number of applications in distributed sensing and machine learning. We show that any limit point of DFAL iterates is optimal; and for any $epsilon>0$, an $epsilon$-optimal and $epsilon$-feasible solution can be computed within $mathcalO(log(epsilo{n}^{-1}))$ DFAL iterations, which require $mathcalO(fracps{i}_{max}^{1.5}{d}_{min}epsilo{n}^{-1})$ proximal gradient computations and communications per node in total, where $ps{i}_{max}$ denotes the largest eigenvalue of the graph Laplacian, and $d_{min}$ is the minimum degree of the graph. We also propose an asynchronous version of DFAL by incorporating randomized block coordinate descent methods; and demonstrate the efficiency of DFAL on large scale sparse-group LASSO problems.

This page was built for publication: An Asynchronous Distributed Proximal Gradient Method for Composite Convex Optimization

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