# Distributed Proximal Gradient Algorithm for Partially Asynchronous Computer Clusters

arXiv: https://arxiv.org/abs/1704.03540 · HTML: https://mlsanity.com/paper/1704.03540/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Apr 2017.

## Built on by (most cited first, 10 of 10)

- [Proximal Gradient Descent-Ascent: Variable Convergence under KL Geometry](https://mlsanity.com/paper/2102.04653/) (2021)
- [A Fast and Convergent Proximal Algorithm for Regularized Nonconvex and Nonsmooth Bi-level Optimization](https://mlsanity.com/paper/2203.16615/) (2022)
- [Fast and Robust Sparsity Learning over Networks: A Decentralized Surrogate Median Regression Approach](https://mlsanity.com/paper/2202.05498/) (2022)
- [FedREP: A Byzantine-Robust, Communication-Efficient and Privacy-Preserving Framework for Federated Learning](https://mlsanity.com/paper/2303.05206/) (2023)
- [Assisted Learning for Organizations with Limited Imbalanced Data](https://mlsanity.com/paper/2109.09307/) (2021)
- [Sharper Bounds for Proximal Gradient Algorithms with Errors](https://mlsanity.com/paper/2203.02204/) (2022)
- [On the Optimal Batch Size for Byzantine-Robust Distributed Learning](https://mlsanity.com/paper/2305.13856/) (2023)
- [Asynchronous Message-Passing and Zeroth-Order Optimization Based Distributed Learning with a Use-Case in Resource Allocation in Communication Networks](https://mlsanity.com/paper/2311.04604/) (2023)
- [Asynchronous Decentralized SGD under Non-Convexity: A Block-Coordinate Descent Framework](https://mlsanity.com/paper/2505.10322/) (2025)
- [A distributed semismooth Newton based augmented Lagrangian method for distributed optimization](https://mlsanity.com/paper/2602.23854/) (2026)

## Abstract (arXiv)

With ever growing data volume and model size, an error-tolerant, communication efficient, yet versatile distributed algorithm has become vital for the success of many large-scale machine learning applications. In this work we propose m-PAPG, an implementation of the flexible proximal gradient algorithm in model parallel systems equipped with the partially asynchronous communication protocol. The worker machines communicate asynchronously with a controlled staleness bound s and operate at different frequencies. We characterize various convergence properties of m-PAPG: 1) Under a general non-smooth and non-convex setting, we prove that every limit point of the sequence generated by m-PAPG is a critical point of the objective function; 2) Under an error bound condition, we prove that the function value decays linearly for every s steps; 3) Under the Kurdyka-Lojasiewicz inequality, we prove that the sequences generated by m-PAPG converge to the same critical point, provided that a proximal Lipschitz condition is satisfied.