New paper simplifies and strengthens hardness of min-max optimization

A new paper by Bernasconi, Castiglioni, Celli, and Farina (arXiv:2411.03248) dramatically simplifies and strengthens the computational complexity results for min-max optimization under coupled constraints. Building on the foundational work of Daskalakis, Skoulakis, and Zampetakis (DSZ21), the authors provide a fundamentally new proof that yields multiple improvements. First, the hardness holds even for objective functions that are degree-2 polynomials of the specific quadratic-linear form, far simpler than previously required. Second, the proof improves parameter dependence and achieves constant inapproximability for gradient descent-ascent when measured in ℓ∞-norm, meaning no algorithm can approximate the optimum within a constant factor. Third, the new proof is much simpler and more elegant than prior approaches.

The paper's second major result is that even convex-concave (bilinear) min-max optimization becomes PPAD-hard under "general constraints" where the min and max players have different constraint sets—a class that includes many real-world game-theoretic models. Along the way, the authors also establish PPAD-membership for a broad class of quasi-variational inequalities, which has implications beyond min-max optimization. These results clarify the fundamental limits of computing equilibria in adversarial machine learning, game theory, and multi-agent systems, where coupled constraints are common. The work suggests that for many practical min-max problems with constraints, exact or near-optimal solutions are computationally intractable even in seemingly benign settings.