The Complexity of Min-Max Optimization for Quadratic Polynomials

TL;DR

We prove that computing approximate stationary points of min-max optimization for quadratic polynomials is PPAD-hard.

Problem

Min-max optimization is important in game theory and machine learning, but its computational complexity for general cases was not well understood. In particular, the complexity of finding stationary points for quadratic polynomials was open.

Approach

The authors construct a reduction from the PPAD-complete Brouwer fixed point problem. They show that the reduction works even for multilinear quadratic polynomials where each variable appears in at most three monomials. Using this result, they also prove the first PPAD-hardness for two-team zero-sum polymatrix games.

Results & Contribution

We prove that computing approximate stationary points of min-max optimization for quadratic polynomials is PPAD-hard, indicating that the problem is unlikely to be solved efficiently. This is a significant theoretical contribution to game theory and optimization.