하위 수준 문제가 제약이 없고 강하게 볼록인 경우, 이계(bilevel) 최적화에서 정상점(stationary points)을 찾는 문제를 고찰한다. 이 문제는 최근 수년 동안 광범위하게 연구되어 왔으며, 주요 기술적 난제는 상위 수준 변수 $x$의 변화에 대한 응답으로 하위 수준 해 $y^{\ast }(x)$를 추적하는 데 있다. 이후 기존의 모든 접근법은 하위 수준 해를 알고 있는 유전(genie) 알고리즘에 분석을 접목시키는 경향이 있으며, 따라서 그와는 멀리 떨어진 어떤 점도 질의할 필요가 없다. 본 연구는 이러한 접근법들과 대비되는 이중(dual) 질문을 다룬다. 즉, $y^{\ast }(x)$에 대한 하위 수준 해를 $O(\epsilon )$의 정확도로 추정해 주는 오라클(oracle), $y^{\ast }$-aware 오라클을 가정하고, 더 나아가 $y^{\ast }(x)$ 주변의 반경 $\Theta (\epsilon )$-볼 안에서 1차 기울기 추정기가 { \it locally unbiased} (국소적으로 불편)하다고 하자. 이러한 $y^{\ast }$-aware 오라클을 이용하여 정상점을 찾는 문제의 복잡도를 연구한다. 우리는 $O({\epsilon }^{-6})$, $O({\epsilon }^{-4})$번의 1차 $y^{\ast }$-aware 오라클 접근을 통해 $\epsilon$-정상점에 수렴하는 간단한 1차 방법을 제안한다. 우리의 상한(upper bounds)은 표준 불편 1차 오라클에도 적용되며, 최소한의 가정 하에서 1차 방법의 최선으로 알려진 복잡도를 $O(\epsilon )$만큼 개선한다. 이어서 각각에 대해, 추가적인 매끄러움(smoothness) 가정이 없는 경우와 있는 경우의 $\Omega ({\epsilon }^{-6})$, $\Omega ({\epsilon }^{-4})$에 해당하는 일치하는 하한(lower bounds)을 제시한다. 우리의 결과는 $y^{\ast }$-aware 오라클을 시뮬레이션하는 어떤 접근법도 동일한 하한을 겪어야 함을 시사한다.

*본 초록은 AI를 통해 원문을 번역한 내용입니다. 정확한 내용은 하기 원문에서 확인해주세요.