# Improved Hardness Results for Min-Max Optimization with Coupled Constraints

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Nov 2024.

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

- [Expected Variational Inequalities](https://mlsanity.com/paper/2502.18605/) (2025)
- [On the Computational Complexity of Performative Prediction](https://mlsanity.com/paper/2601.20180/) (2026)
- [Min-Max Optimization Requires Exponentially Many Queries](https://mlsanity.com/paper/2605.13806/) (2026)
- [The Complexity of Min-Max Optimization for Quadratic Polynomials](https://mlsanity.com/paper/2606.17000/) (2026)
- [Nash Equilibria in Games with Playerwise Concave Coupling Constraints: Existence and Computation](https://mlsanity.com/paper/2509.14032/) (2025)

## Abstract (arXiv)

We investigate the computational complexity of min-max optimization under coupled constraints. The work of Daskalakis, Skoulakis, and Zampetakis [DSZ21] was the first to study min-max optimization through the lens of computational complexity, showing that min-max problems with nonconvex-nonconcave objectives are PPAD-hard under coupled constraints. By carefully exploiting the coupled constraints rather than the structure of the objective function, we are able to significantly simplify and strengthen the proof of the hardness result. More precisely, the first contribution of this paper is a fundamentally new proof of their main result, which improves it in multiple directions: it holds for degree-2 polynomials which are quadratic-linear, it improves the dependence on the parameters of the problem (also yielding constant inapproximability for gradient descent-ascent in ℓ_∞-norm), and it is much simpler than previous approaches. Second, we show that with general constraints (i.e., the min player and max player have different constraints), even convex-concave (bilinear) min-max optimization becomes PPAD-hard. Along the way, we also provide PPAD-membership of a general problem related to quasi-variational inequalities, which has applications beyond our problem.