The Complexity of Min-Max Optimization for Quadratic Polynomials

Martino Bernasconi, Matteo Castiglioni, Andrea Celli +1

We prove that computing approximate stationary points of min-max optimization over the hypercube is PPAD-hard for quadratic polynomials. This holds even when the polynomials are mu…