# Convergence of the Chambolle-Pock Algorithm in the Absence of Monotonicity

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 75 references that are in the map.
- First posted on arXiv 11 Dec 2023.

## Builds on (most cited first, 15 of 15)

- [Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization](https://mlsanity.com/paper/2011.00364/) (2020)
- [Generalized monotone operators and their averaged resolvents](https://mlsanity.com/paper/1902.09827/) (2019)
- [Solving Nonconvex-Nonconcave Min-Max Problems exhibiting Weak Minty Solutions](https://mlsanity.com/paper/2201.12247/) (2022)
- [Solving stochastic weak Minty variational inequalities without increasing batch size](https://mlsanity.com/paper/2302.09029/) (2023)
- [Escaping limit cycles: Global convergence for constrained nonconvex-nonconcave minimax problems](https://mlsanity.com/paper/2302.09831/) (2023)
- [Global convergence of splitting methods for nonconvex composite optimization](https://mlsanity.com/paper/1407.0753/) (2014)
- [Convergence of Proximal Point and Extragradient-Based Methods Beyond Monotonicity: the Case of Negative Comonotonicity](https://mlsanity.com/paper/2210.13831/) (2022)
- [The proximal alternating direction method of multipliers in the nonconvex setting: convergence analysis and rates](https://mlsanity.com/paper/1801.01994/) (2018)
- [Asymmetric Forward-Backward-Adjoint Splitting for Solving Monotone Inclusions Involving Three Operators](https://mlsanity.com/paper/1602.08729/) (2016)
- [The Primal-Dual Hybrid Gradient Method for Semiconvex Splittings](https://mlsanity.com/paper/1407.1723/) (2014)
- [Degenerate Preconditioned Proximal Point algorithms](https://mlsanity.com/paper/2109.11481/) (2021)
- [Convergence of the Preconditioned Proximal Point Method and Douglas-Rachford Splitting in the Absence of Monotonicity](https://mlsanity.com/paper/2305.03605/) (2023)
- [Analytical solutions to some optimization problems on ranks and inertias of matrix-valued functions subject to linear matrix inequalities](https://mlsanity.com/paper/1301.0986/) (2013)
- [On the improved conditions for some primal-dual algorithms](https://mlsanity.com/paper/2201.00139/) (2022)
- [The Non-Strict Projection Lemma](https://mlsanity.com/paper/2305.08735/) (2023)

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

- [Spingarn's Method and Progressive Decoupling Beyond Elicitable Monotonicity](https://mlsanity.com/paper/2504.00836/) (2025)

## Abstract (arXiv)

The Chambolle-Pock algorithm (CPA), also known as the primal-dual hybrid gradient method, has gained popularity over the last decade due to its success in solving large-scale convex structured problems. This work extends its convergence analysis for problems with varying degrees of (non)monotonicity, quantified through a so-called oblique weak Minty condition on the associated primal-dual operator. Our results reveal novel stepsize and relaxation parameter ranges which do not only depend on the norm of the linear mapping, but also on its other singular values. In particular, in nonmonotone settings, in addition to the classical stepsize conditions, extra bounds on the stepsizes and relaxation parameters are required. On the other hand, in the strongly monotone setting, the relaxation parameter is allowed to exceed the classical upper bound of two. Moreover, we build upon the recently introduced class of semimonotone operators, providing sufficient convergence conditions for CPA when the individual operators are semimonotone. Since this class of operators encompasses traditional operator classes including (hypo)- and co(hypo)-monotone operators, this analysis recovers and extends existing results for CPA. Tightness of the proposed stepsize ranges is demonstrated through several examples.