기술 요약: 미니맥스와 제약 하위 문제를 갖는 바이레벨 최적화를 위한 페널티 기반 1 차 방법

문제 공식화

본 논문은 상위 문제와 하위 문제 모두 미니맥스 (minimax) 구조를 보이는 바이레벨 최적화 문제的一类를 다룹니다. 일반적인 공식화는 다음과 같이 정의됩니다:
$$\min_{x_1, y_1, y_2} \left\{ \max_{x_2} f(x_1, x_2, y_1, y_2) \mid (y_1, y_2) \in \arg\min_{z_1} \max_{z_2} \tilde{f}(x_1, z_1, z_2) \right\}$$
여기서 $(y_1, y_2)$는 하위 함수 $\tilde{f}$의 안장점 (saddle-point) 을 나타냅니다. 저자들은 특정 구조적 속성을 가정합니다: $f$와 $\tilde{f}$는 매끄러운 성분과 적절한 닫힌 볼록 함수로 분해될 수 있으며, 각각의 변수에 대해 특정 볼록성/오목성 속성을 가집니다 (예: $\tilde{f}$는 $y_1$에 대해 볼록하고 $y_2$에 대해 오목함).

이 연구의 중요한 하위 집합은 하위 문제가 볼록 비선형 부등식 제약이 있는 볼록 최소화 문제인 바이레벨 문제에 초점을 맞춥니다:
$$\min_{x_1, y_1} \left\{ f(x_1, y_1) \mid y_1 \in \arg\min_{z_1} \{ \bar{f}(x_1, z_1) \mid \bar{g}(x_1, z_1) \leq 0 \} \right\}$$
슬레이터 (Slater) 조건 하에서, 이 제약 문제는 라그랑주 쌍대성을 통해 일반적인 미니맥스 바이레벨 프레임워크의 특수한 경우로 재형성됩니다.

기존 문헌은 주로 하위 문제가 단일 목적 함수 최소화 (종종 강한 볼록성) 인 바이레벨 최적화에 집중합니다. 하이퍼그래디언트나 암시적 미분에 의존하는 방법들은 하위 문제가 단순히 볼록하거나, 비볼록이거나, 미니맥스 구조를 가질 경우 종종 실패합니다. 본 연구는 하위 문제에 강한 볼록성이 필요하지 않은 미니맥스 하위 문제 설정에 대한 1 차 방법들을 개발함으로써 이러한 간극을 메우려는 것입니다.

방법론

제안된 접근법은 **값 함수 페널티 재형성 (value-function penalty reformulation)**을 활용합니다. 페널티 매개변수 $\rho$를 도입하여 제약 바이레벨 문제를 비제약 (또는 더 간단한 제약) 미니맥스 문제로 변환합니다.

결정론적 설정

1. 페널티 재형성: 원래 문제는 단일 수준 미니맥스 문제로 재형성됩니다:
   $$\min_{x_1, y_1, y_2} \max_{x_2, z_1, z_2} P_\rho(x_1, x_2, y_1, y_2, z_1, z_2)$$
   여기서 $P_\rho$는 목적 함수와 하위 문제의 쌍대 간격을 나타내는 페널티 항 $\rho(p(x_1, y_1) - d(x_1, y_2))$을 포함합니다.
2. 알고리즘: 저자들은 **부정확한 근접점 방법 (inexact proximal point method)**을 제안합니다. 외부는 강한 볼록 - 강한 오목 (SCSC) 부분 문제를 일련으로 풀면서 원 - 쌍대 변수를 업데이트합니다.
3. 부분 문제 솔버: 각 부분 문제는 최적 1 차 방법 (구체적으로 Lu 와 Mei [52] 또는 Kovalev 와 Gasnikov [37]의 방법 변형) 인 OptFOM을 사용하여 풀립니다.
4. 복잡도: 이 방법은 $\tilde{O}(\epsilon^{-4})$의 오라클 복잡도로 $\epsilon$-KKT 점을 찾습니다.

확률적 설정

매끄러운 성분에 대해 확률적 그래디언트 오라클만 사용 가능한 경우:

1. 알고리즘: 결정론적 근접점 방법은 내부 부분 문제를 풀기 위해 확률적 가속 원 - 쌍대 (SAPD) 방법 (구체적으로 Zhang 등 [75]의 SAPD+) 를 사용하도록 적응됩니다.
2. 수렴: 이 방법은 정확한 $\epsilon$-KKT 점으로부터 $\epsilon$ 거리 이내인 "거의" $\epsilon$-KKT 점을 $\tilde{O}(\epsilon^{-9})$의 확률적 오라클 복잡도로 찾습니다.

제약 하위 문제에의 적용

제약이 있는 볼록 하위 문제 (문제 4) 를 갖는 바이레벨 최적화의 특정 경우에 대해, 저자들은 슬레이터 조건 하에서 라그랑주 승수가 상자 $[0, B]^l$ 내에서 유계임을 보입니다. 이는 쌍대 변수를 상자 제약이 있는 명시적 최적화 변수로 도입함으로써 제약 문제를 일반적인 미니맥스 바이레벨 문제 (문제 1) 로 재형성할 수 있게 합니다. 이 재형성은 내부 페널티 매개변수의 필요성을 제거하여 기존 연구에 비해 개선된 복잡도 상한을 이끌어냅니다.

주요 기여

1. 바이레벨 미니맥스에 대한 첫 번째 복잡도 결과: 본 논문은 하위 문제가 미니맥스 문제인 바이레벨 최적화에 대한 결정론적 및 확률적 1 차 방법의 첫 번째 복잡도 상한을 확립합니다.
   • 결정론적 복잡도: $\tilde{O}(\epsilon^{-4})$.
   • 확률적 복잡도: $\tilde{O}(\epsilon^{-9})$.
2. 제약 바이레벨 문제에 대한 개선된 상한: 볼록 제약 하위 문제를 갖는 바이레벨 문제를 제안된 미니맥스 프레임워크의 사례로 재형성함으로써, 저자들은 $\tilde{O}(\epsilon^{-4})$의 복잡도를 달성합니다. 이는 단순히 볼록한 하위 문제에 대한 기존 결과 ($\tilde{O}(\epsilon^{-7})$, [53]) 와 강한 볼록 하위 문제에 대한 결과 ($\tilde{O}(\epsilon^{-6})$, [51]) 보다 개선된 것입니다. 이 개선은 이전에는 더 높은 매끄러움 매개변수로 이어졌던 내부 제약에 대한 두 번째 페널티 매개변수 사용을 피함으로써 비롯됩니다.
3. 실증적 검증:
   • 합성 데이터: 제약 선형 바이레벨 문제에서 제안된 방법은 Lipschitz 상수가 조정될 때 특히 기존 페널티 기반 방법 (FOP 및 SMO) 에 비해 경쟁력 있는 수렴 속도를 보여줍니다.
   • 실제 응용: 이 방법은 딥러닝의 **분포 강건 최적화 (DRO)**를 위한 하이퍼파라미터 튜닝에 적용됩니다. CelebA 및 Waterbirds 데이터셋에서 제안된 확률적 바이레벨 접근법은 평균 정확도를 유지하면서 기존 DRO 방법보다 더 나은 최악 그룹 (worst-group) 정확도를 달성합니다.

결과 및 의의

본 논문은 제안된 페널티 기반 프레임워크가 1 차 복잡도 측면에서 문헌에서 아직 탐구되지 않았던 미니맥스 구조를 갖는 바이레벨 문제를 처리하는 통합된 접근법을 제공한다고 주장합니다.

• 이론적 의의: 이 작업은 바이레벨 최적화와 미니맥스 최적화 간의 간극을 메우며, 하위 문제에 대한 강한 볼록성 가정에 의존하지 않고 엄격한 수렴 보장을 제공합니다. 제약 하위 문제에 대한 복잡도를 $\tilde{O}(\epsilon^{-7})$에서 $\tilde{O}(\epsilon^{-4})$로 줄인 것은 중요한 이론적 진전으로 제시됩니다.
• 실용적 의의: DRO 에의 응용은 분포 이동 및 그룹 공정성과 관련된 머신러닝 시나리오에서 이 방법의 유용성을 보여줍니다. CelebA 및 Waterbirds 데이터셋에 대한 결과는 이 방법이 "최악 그룹" 최적화 과제를 효과적으로 처리하여 기준 DRO 방법보다 더 높은 최악 그룹 정확도를 달성할 수 있음을 보여줍니다.

저자들은 컴팩트한 실행 가능 도메인 필요성, KKT 정의에 대한 리프트된 공간 (lifted space) 사용, 그리고 확률적 경우의 높은 복잡도 ($\tilde{O}(\epsilon^{-9})$) 를 포함한 한계를 인정하며, 분산 감소 기법이 향후 연구 방향이 될 수 있음을 지적합니다.