An Asynchronous Distributed Proximal Gradient Method for Composite Convex Optimization

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 $\mathcal{O}(\log ({\epsilon }^{-1}))$ DFAL iterations, which require $\mathcal{O}(\frac{{\psi }_{\max }^{1.5}}{d_{\min }}{\epsilon }^{-1})$ proximal gradient computations and communications per node in total, where ${\psi }_{\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.

The manuscript will appear in the Proceedings of the 32nd International Conference on Machine Learning, Lille, France, 2015. JMLR: W&CP volume 37. Copyright 2015 by the author(s)

References in corpus (1)

• An Augmented Lagrangian Method for Conic Convex Programming

Cited by in corpus (6)

• Distributed and Inexact Proximal Gradient Method for Online Convex Optimization
• Asynchronous Online Federated Learning for Edge Devices with Non-IID Data
• Asynchronous Federated Learning for Sensor Data with Concept Drift
• Proximal SCOPE for Distributed Sparse Learning: Better Data Partition Implies Faster Convergence Rate
• Semidefinite Programming For Chance Constrained Optimization Over Semialgebraic Sets
• Asynchronous Multi-Task Learning