본 연구에서는 목적함수는 양 수준 모두에서 매끄럽지만 비볼록일 수 있으며, 변수는 닫힌 볼록집합으로 제한되는 이계 최적화(Bilevel Optimization, BO)를 해결하기 위한 1차 알고리즘을 연구한다. 첫 단계로, 상위-수준과 하위-수준 목적함수를 가중합으로 결합하고 패널티 매개변수 σ>0을 사용하는 패널티 방법의 관점에서 BO의 경관(landscape)을 연구한다. 특히, 패널티 함수와 하이퍼-목적(hyper-objective) 간의 강한 연관성을 확립하며, 두 값과 도함수가 O(σ)만큼 서로 근접해야 하는 조건을 명시적으로 특성화함으로써 이를 보인다. 분석의 부수 결과로, 하위-수준 문제가 최소한의 조건 하에서 다중 해를 가질 때 하이퍼-목적의 그래디언트에 대한 명시적 공식을 도출하며, 이는 독립적인 관심사일 수 있다. 다음으로, 패널티 정식을 원래 BO의 O(σ) 근사로 간주하여, σ=O(ε)로 패널티 정식을 최적화함으로써 ε-정류(ε-stationary) 해를 찾는 1차 알고리즘을 제안한다. 교란된 하위-수준 문제가 소(小)오차 근접 오차 경계(error bound, EB) 조건을 균일하게 만족할 때, 패널티 함수의 ε-정류 점으로 수렴하는 1차 알고리즘을 제안하며, 오라클이 결정론적일 때 총 O(ε^{-3}), 오라클이 잡음(noisy)일 때 총 O(ε^{-7})의 1차(확률적) 그래디언트 오라클 접근을 사용한다. 확률적 오라클에 대한 추가 가정 하에서, 알고리즘은 완전한 {\it single-loop} 방식으로 구현될 수 있음을 보이는데, 즉 반복당 O(1)개의 샘플만으로 수행되며, 각각 O(ε^{-3}) 및 O(ε^{-5})의 향상된 오라클 복잡도(oracle-complexity)를 달성한다.

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