An asynchronous distributed proximal gradient method for composite convex optimization

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 ∈ > 0, an ∈-optimal and e-feasible solution can be computed within O(log(∈^-1)) DFAL iterations, which require O(ψ^1.5_max/d_m ∈^-1) proximal gradient computations and communications per node in total, where ψ_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.