The Complexity of Min-Max Optimization for Quadratic Polynomials
Martino Bernasconi, Matteo Castiglioni, Andrea Celli, Alexandros Hollender
이차 다항식에 대한 미니맥스 최적화에서 근사 정류점 계산이 PPAD-난해임을 증명했다.
미니맥스 최적화는 게임 이론과 머신러닝에서 중요한 문제이지만, 일반적인 경우 계산 복잡도가 잘 알려져 있지 않았다. 특히 이차 다항식에 대해서도 정류점을 찾는 문제의 복잡도가 미해결이었다.
저자들은 PPAD-완전 문제인 Brouwer 고정점 문제로부터 환원을 구성했다. 이차 다항식이 다중선형이고 각 변수가 최대 3개의 단항식에 나타나는 특별한 경우에도 환원이 가능함을 보였다. 또한, 이 결과를 이용해 두 팀 제로섬 폴리매트릭스 게임의 PPAD-난해성을 처음으로 증명했다.
이차 다항식 미니맥스 최적화의 근사 정류점 계산이 PPAD-난해임을 증명하여, 해당 문제가 효율적으로 해결되기 어려움을 보였다. 이는 게임 이론과 최적화 이론에 중요한 이론적 기여를 한다.