Minimax 및 제약 하위 레벨 문제를 갖는 이중 레벨 최적화에 대한 페널티 기반 1차 방법

우리는 상위 레벨 문제와 하위 레벨 문제 모두 minimax 구조를 가지는 일련의 이중 레벨 최적화 문제를 연구합니다. 이 설정은 광범위한 신흥 응용 분야를 포착합니다. 이중 레벨 최적화 및 minimax 최적화에 대한 방대한 문헌에도 불구하고, 기존 방법들은 주로 하위 레벨 최소화 문제를 갖는 이중 레벨 최적화에 초점을 맞추고 있으며, 종종 강한 볼록성(strong convexity) 가정을 전제로 합니다. 따라서 본문에서 고려하는 minimax 하위 레벨 설정에는 직접적으로 적용할 수 없습니다. 이러한 격차를 해소하기 위해, 우리는 하위 레벨 문제의 강한 볼록성을 요구하지 않는 이중 레벨 minimax 최적화를 위한 페널티 기반 1차 방법을 개발합니다. 결정론적(deterministic) 설정에서, 제안된 방법이 $ ilde{O}(\epsilon^{-4})$ 오라클 복잡도로 $\epsilon$-KKT 지점을 찾는다는 것을 확립합니다. 나아가, 볼록 제약 하위 레벨 최소화를 갖는 이중 레벨 문제는 라그랑주 쌍대성(Lagrangian duality)을 통해 우리 프레임워크의 특수 사례로 재정식화될 수 있음을 보여주며, 이는 기존 $ ilde{O}(\epsilon^{-7})$ 결과보다 개선된 $ ilde{O}(\epsilon^{-4})$ 복잡도 경계로 이어집니다. 마지막으로, 우리는 오직 확률적 기울기(stochastic gradient) 오라클만 사용 가능한 확률적 설정(stochastic setting)으로 접근 방식을 확장하고, 제안된 확률적 방법이 $ ilde{O}(\epsilon^{-9})$ 오라클 복잡도로 거의 $\epsilon$-KKT 지점을 찾는다는 것을 증명합니다.