요약

본 논문은 $[0,1]^d imes [0,1]^d$ 상의 비볼록-비오목(nonconvex-nonconcave) 함수 $f$의 min-max 최적화에 대한 쿼리 복잡도를 분석합니다. 오라클 접근을 통해 $f$와 그 기울기 $ abla f$를 사용할 수 있는 경우에도, $\varepsilon$-근사 정지점(stationary point)을 찾는 모든 알고리즘은 $1/\varepsilon$ 또는 차원 $d$에 대해 지수적인 횟수의 쿼리를 수행해야 함을 증명합니다.

핵심 포인트

• 비볼록-비오목 함수 $f$의 min-max 최적화는 높은 쿼리 복잡도를 가집니다.
• 함수 $f$와 그 기울기 $ abla f$에 대한 오라클 접근이 주어져도 지수적인 쿼리가 필요합니다.
• $\varepsilon$-근사 정지점을 찾는 알고리즘은 $1/\varepsilon$ 또는 차원 $d$에 대해 지수적 복잡도를 가집니다.