# A Simple Parallel Algorithm with an O(1/t) Convergence Rate for General Convex Programs

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Dec 2015.

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

- [Policy Optimization for Constrained MDPs with Provable Fast Global Convergence](https://mlsanity.com/paper/2111.00552/) (2021)
- [Anchor-Changing Regularized Natural Policy Gradient for Multi-Objective Reinforcement Learning](https://mlsanity.com/paper/2206.05357/) (2022)
- [First-Order Algorithms for Nonlinear Generalized Nash Equilibrium Problems](https://mlsanity.com/paper/2204.03132/) (2022)
- [A single-loop SPIDER-type stochastic subgradient method for expectation-constrained nonconvex nonsmooth optimization](https://mlsanity.com/paper/2501.19214/) (2025)
- [Decentralized Multi-Task Stochastic Optimization With Compressed Communications](https://mlsanity.com/paper/2112.12373/) (2021)
- [Damped Proximal Augmented Lagrangian Method for weakly-Convex Problems with Convex Constraints](https://mlsanity.com/paper/2311.09065/) (2023)

## Abstract (arXiv)

This paper considers convex programs with a general (possibly non-differentiable) convex objective function and Lipschitz continuous convex inequality constraint functions. A simple algorithm is developed and achieves an O(1/t) convergence rate. Similar to the classical dual subgradient algorithm and the ADMM algorithm, the new algorithm has a parallel implementation when the objective and constraint functions are separable. However, the new algorithm has a faster O(1/t) convergence rate compared with the best known O(1/√t) convergence rate for the dual subgradient algorithm with primal averaging. Further, it can solve convex programs with nonlinear constraints, which cannot be handled by the ADMM algorithm. The new algorithm is applied to a multipath network utility maximization problem and yields a decentralized flow control algorithm with the fast O(1/t) convergence rate.