# A Primal-Dual Parallel Method with O(1/ε) Convergence for Constrained Composite Convex Programs

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Jul 2017.

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

- [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)
- [Nonsmooth Projection-Free Optimization with Functional Constraints](https://mlsanity.com/paper/2311.11180/) (2023)

## Abstract (arXiv)

This paper considers large scale constrained convex (possibly composite and non-separable) programs, which are usually difficult to solve by interior point methods or other Newton-type methods due to the non-smoothness or the prohibitive computation and storage complexity for Hessians and matrix inversions. Instead, they are often solved by first order gradient based methods or decomposition based methods. The conventional primal-dual subgradient method, also known as the Arrow-Hurwicz-Uzawa subgradient method, is a low complexity algorithm with an O(1/ε2) convergence time. Recently, a new Lagrangian dual type algorithm with a faster O(1/ε) convergence time is proposed in Yu and Neely (2017). However, if the objective or constraint functions are not separable, each iteration of the Lagrangian dual type method in Yu and Neely (2017) requires to solve a unconstrained convex program, which can have huge complexity. This paper proposes a new primal-dual type algorithm with O(1/ε) convergence for general constrained convex programs. Each iteration of the new algorithm can be implemented in parallel with low complexity even when the original problem is composite and non-separable.