Extragradient methods with complexity guarantees for hierarchical variational inequalities

기술 요약: 계층적 변분 부등식을 위한 복잡도 보장을 갖는 외구경법(Extragradient Methods)

문제 정식화
본 논문은 실 분리 가능한 힐베르트 공간 $Z$ 내에서 계층적 평형 문제를 해결하는 문제를 다룬다. 핵심 목표는 다른 HVI(hemi-variational inequality)의 해집합 위에서 정의된 HVI의 해 $z^*$를 찾는 것이다. 공식적으로 문제 (P)는 다음과 같다:
$z^* \in S_2$를 찾는 것, 여기서 $S_2 = \text{zer}(F_2 + \partial \ell_2)$는 하위 레벨 HVI의 해집합이며, 모든 $z \in S_2$에 대하여 다음을 만족한다:
$$\langle F_1(z^*), z - z^* \rangle + \ell_1(z) - \ell_1(z^*) \geq 0$$
여기서 $F_1, F_2$는 단조 연산자(monotone operators)이고, $\ell_1, \ell_2$는 적절하고(proper), 볼록하며(convex), 하반연속(lower-semicontinuous)인 함수들이다.

이 정식화는 다음과 같은 여러 문제 클래스를 통합한다:

• 단순 이중 레벨 최적화 (여기서 $\ell_1, \ell_2$는 매끄럽거나(smooth) 합성적(composite)임)
• 중첩된 변분 부등식 (여기서 $\ell_1=0$이고 $\ell_2$는 지시 함수(indicator function)임)
• 계층적 합동 볼록 일반화 나쉬 평형 문제(GNEP)
• VI 제약 조건하의 최적 제어

방법론
저자들은 티코노프 정규화(Tikhonov regularization)에 기반한 낙관적 외구경법(Optimistic Extragradient Method) (알고리즘 1)을 제안한다. 이전의 접근 방식들(예: 표준 외구경법)이 반복당 두 번의 연산자 평가를 요구하는 것과 달리, 이 방법은 계산 비용을 반복당 단 한 번의 연산자 평가로 줄이기 위해 "과거"의 연산자 평가를 활용한다.

알고리즘은 정규화된 연산자 $V_k = F_2 + \sigma_k F_1$와 정규화된 함수 $G_k = \ell_2 + \sigma_k \ell_1$를 구성하며, 여기서 $(\sigma_k)$는 0으로 수렴하는 감소하는 정규화 수열이다. 반복 스킴은 다음과 같다:

1. 예측(Prediction): $z_{k+1/2} = \text{prox}_{t_k G_k}(z_k - t_k (F_2(z_{k-1/2}) + \sigma_k F_1(z_{k-1/2})))$
2. 수정(Correction): $z_{k+1} = \text{prox}_{t_k G_k}(z_k - t_k (F_2(z_{k+1/2}) + \sigma_k F_1(z_{k+1/2})))$

분석은 특정 기하학적 가정들에 의존한다:

• 약한 날카로움(Weak Sharpness): 하위 레벨 해집합 $S_2$는 갭 함수(gap function)와 해집합으로부터의 거리를 연결하는 $(\alpha, \rho)$-약한 날카로움 조건을 만족한다고 가정된다.
• Attouch-Czarnecki 조건: 반복 단계 크기(step sizes)와 정규화 파라미터에 대한 합산 가능성(summability) 조건이 반복 횟수의 유계성(boundedness)을 보장하기 위해 부과된다.
• 계층적 일관성(Hierarchical Coherence): 상위 레벨 함수의 도메인이 하위 레벨 도메인에 포함됨을 보장하는 조건이다.

주요 기여

1. 일반적인 문제 정식화: 본 논문은 유한 차원에서의 지시 함수 대신, 무한 차원 힐베르트 공간 내의 일반적인 볼록 합성 항 $\ell_1, \ell_2$를 다룸으로써 기존 문헌([1, 57])을 확장한다.
2. 알고리즘 효율성: 제안된 방법은 반복당 $F_1, F_2$의 연산자를 한 번만 평가하며, 이는 이전 연구에서 사용된 이중 호출 외구경법보다 개선된 것이다.
3. 복잡도 보장: 저자들은 적절하게 구성된 에르고딕 평균(ergodic averages)을 사용하여 하위 레벨(실행 가능성 갭)과 계층적 문제(최적성 갭) 모두에 대한 최악의 경우 반복 복잡도율을 확립한다.
4. 콤팩트성 가정 제거: 콤팩트한 도메인을 요구했던 기존의 복잡도 분석들과 달리, 본 연구는 기하학적 약한 날카로움과 점근적 분석 기술을 활용하여 콤팩트한 도메인 가정 없이 수렴 속도를 도출한다.

주요 결과
논문은 알고리즘에 의해 생성된 에르고딕 평균 $\bar{z}_K$에 대한 아순선형(sublinear) 수렴 속도를 확립한다. $\sigma_k = O(k^{-\delta})$ ($\delta \in (0,1)$)인 정규화 수열을 가정할 때:

• 실행 가능성 갭(Feasibility Gap): 하위 레벨 문제의 갭 함수는 $O(k^{-\delta})$의 속도로 수렴한다.
• 최적성 갭(Optimality Gap): 전체 계층적 문제의 갭 함수는 $O(k^{-(1-\delta)})$의 속도로 수렴한다.
• 개선된 속도: 상위 레벨 연산자 $F_1$이 강한 단조성(strongly monotone)을 가진다는 가정하에, 논문은 고유한 해로의 수렴을 보여주는 개선된 속도를 도출한다.
• 약한 수렴(Weak Convergence): 기하학적 약한 날카로움 조건 하에서, 반복 횟수 시퀀스는 $S_1$의 해로 약하게 수렴함이 입증된다.

의의 및 주장
저자들은 자신들의 결과가 반복 복잡도와 문제 정식화의 일반성 측면에서 최신 기술(state of the art)과 일치하거나 이를 능가한다고 주장한다. 구체적으로, 본 논문은:

• 단순 이중 레벨 최적화 및 특정 VI 케이스로부터 광범위한 계층적 HVI 문제로 복잡도 보장을 확장한다.
• 계층적 최적화에서 주로 사용되었던 "약한 날카로움" 조건이 통합된 복잡도 진술을 확립하기 위해 변분 설정으로 효과적으로 번역될 수 있음을 입증한다.
• 비자율 진화 방정식(non-autonomous evolution equation) 분석 기술을 사용하여 유계되지 않은 도메인을 처리하는 방법론적 프레임워크를 제공하며, 저자들은 이것이 다른 계층적 평형 문제에도 유용할 수 있다고 제안한다.

논문은 현재 분석이 결정론적 설정을 다루고 있지만, 향후 연구에서는 확률적 정식화와 가속화된 방법들을 탐구할 수 있음을 언급하며 마무리된다. 계층적 나쉬 평형 및 제약된 min-max 문제(Generalized Absolute Value Equations 포함)에 대한 수치 실험이 이론적 발견을 검증하기 위해 제시된다.