[Computer-Assisted Proofs in Optimization] Operator Splitting Performance Estimation Problem - 2

이제 본격적으로 논문을 읽어보자. 논문에서는 예시 문제를 Davis-Yin Splitting (DYS)로 두고 문제를 해결한다.

하지만 이 글에서는 예시 문제를 Douglas-Rachford Splitting (DRS)로 두고 해결하고자 한다. 이유는

• 일단 나도 손계산 연습을 해보고 싶고, operator가 3개인 DYS보다는 2개인 DRS가 간단함
• 앞선 글에서 DRS를 어느 정도 설명했으니 독자가 이해하기도 편할 것
• 이 논문의 Theorem 4에서 DRS에 대한 정리를 하는데, 직접 코드를 짜서 verify 해보고 싶음
• 그리고 솔직히 논문 내용 그대로 옮기면 재미없음 ㄹㅇㅋㅋ 대신 흐름은 그대로 유지할 것

이번 글에서는 다음 주제를 다룬다.

• Operator Splitting Performance Estimation Problem을 SDP로 변환하는 방법
• OSPEP로 얻어진 SDP의 Dual Problem과 그 의미 및 활용법

 

Part 1 : Operator Splitting Performance Estimation Problem to SDP

먼저 DRS를 다시 볼 필요가 있다. 우리는 $R_{\alpha A}R_{\alpha B}$가 nonexpansive operator이므로, 이를 $I$와 함께 섞어서 $$\frac{1}{2} I + \frac{1}{2} R_{\alpha A} R_{\alpha B}$$로 fixed point iteration을 돌렸다. 하지만 굳이 이렇게 섞을 필요는 당연히 없고, $\theta \in (0, 2)$에 대하여 $$\frac{2 - \theta}{2} I + \frac{\theta}{2} R_{\alpha A} R_{\alpha B}$$로 섞어도 된다. 여기에 $R_{\alpha A} = 2J_{\alpha A} - I$, $R_{\alpha B} = 2J_{\alpha B} - I$를 대입하면 $$I - \theta J_{\alpha B} + \theta J_{\alpha A} (2J_{\alpha B} - I)$$를 우리의 operator로 얻는다. 이제 목표는 이 operator가 "얼마나 contractive"한지 파악하는 것이다.

 

우리는 Performance Estimation Problem의 작은 문제에서 $\mathcal{F}_{\mu ,L}$에서 문제를 생각했다.

이번에 다루어 볼 operator class를 알아보자. 앞에서 정의한 네 가지 operator class들과 이들의 교집합을 생각한다.

• maximal monotone operator의 집합 $\mathcal{M}$
• $\mu$-strongly monotone이면서 maximal monotone인 operator의 집합 $\mathcal{M}_\mu$
• $L$-Lipschitz operator의 집합 $\mathcal{L}_L$
• $\beta$-cocoercive operator의 집합 $\mathcal{C}_{\beta}$

 

이제 본격적으로 문제를 서술할 준비가 되었다. $\mathcal{Q}_1, \mathcal{Q}_2$가 각각 operator class고, (단, 이들은 $\mathcal{M}$의 subset) $$T(z ; A, B, \alpha, \theta) = I - \theta J_{\alpha B} + \theta J_{\alpha A} (2J_{\alpha B} - I)$$이라 하자. 우리가 풀고자 하는 최적화 문제는, 고정된 $\alpha, \theta > 0$에 대하여, $$\begin{equation*} \begin{aligned} \text{maximize} \quad & \frac{ ||T(z;A,B,\alpha, \theta) - T(z';A,B,\alpha,\theta)||^2}{||z-z'||^2} \\ \text{subject to} \quad & A \in \mathcal{Q}_1, B \in \mathcal{Q}_2, z \neq z' \end{aligned} \end{equation*}$$이다. 즉, 최악의 경우에서도 $T$를 $L$-Lipschitz라고 부를 수 있는 가장 최적의 $L$을 구하는 것이다.

 

이제 문제를 조금씩 변형해가며 SDP로 만들어보자. Performance Estimation Problem과 크게 다르지 않다.

 

Step 1 : $T(z; A, B, \alpha, \theta)$를 표현하기 위해서, 다음과 같이 변수를 설정한다. $$z_B = J_{\alpha B} z, \quad z_A = J_{\alpha A}(2z_B - z), \quad T(z;A,B,\alpha, \theta) = z - \theta (z_B - z_A)$$

 

Step 2 : 분모에 있는 $||z-z'||^2$가 불편하다. 이를 일반성을 잃지 않고 $1$로 강제하고 싶은 마음이 자연스럽다.

다행히도 이는 가능하다. Operator class $\mathcal{Q}$가 임의의 $\gamma > 0$에 대하여 $$A \in \mathcal{Q} \iff (\gamma^{-1}I)A(\gamma I) \in \mathcal{Q}$$라면 $\mathcal{Q}$를 homogeneous 하다고 한다. 우리가 다루는 operator class는 전부 homogeneous.

이제 $\gamma = ||z-z'||$라고 하면, $z$들을 전부 $\gamma^{-1}z$로 교체하고 $A, B$를 $(\gamma^{-1} I)A(\gamma I)$, $(\gamma^{-1} I)B(\gamma I)$로 교체하자.

이래도 문제 없음은 homogeneous 성질에서 나온다. 또한, Step 1에서 얻은 식 정리를 그대로 사용해도 괜찮다는 것을 열심히 계산하면 알 수 있다.

결국 $||z-z'||=1$인 경우에서만 문제를 해결해도 무방하다는 사실을 얻는다. 제약 조건을 하나 추가하고, 분모를 날리자.

 

중간 점검을 하자면, 결국 우리가 풀 문제는 $$\begin{equation*} \begin{aligned} \text{maximize} \quad & ||z - \theta (z_B - z_A) - z' + \theta(z'_B - z'_A)||^2 \\ \text{subject to} \quad & A \in \mathcal{Q}_1, B \in \mathcal{Q}_2, ||z-z'||^2 = 1 \\ \quad & z_B = J_{\alpha B} z, z_A = J_{\alpha A}(2z_B - z) \\ \quad & z'_B = J_{\alpha B} z', z'_A = J_{\alpha A}(2z'_B- z') \end{aligned} \end{equation*}$$

 

Step 3 : 이제 슬슬 operator class $\mathcal{Q}$가 눈에 거슬린다. Interpolation의 아이디어를 적용하면 좋겠다.

뒤에서 Interpolation을 적용할 때 알게 되겠지만, 필요한 것은 두 점에 대한 Interpolation 조건이다.

즉, Graph에 $(x_1, q_1), (x_2, q_2)$가 속하는 operator $T \in \mathcal{Q}$가 존재할 조건만이 필요하다. 결론을 제시하면,

• $\mathcal{M}$ : $\langle q_1 - q_2, x_1 - x_2 \rangle \ge 0$
• $\mathcal{M}_\mu$ : $\langle q_1 - q_2 , x_1 - x_2 \rangle \ge \mu ||x_1 - x_2||^2$
• $\mathcal{C}_{\beta}$ : $\langle q_1 - q_2, x_1 - x_2 \rangle \ge \beta || q_1 - q_2||^2$
• $\mathcal{L}_L$ : $||q_1- q_2||^2 \le L^2 ||x_1 - x_2||^2$
• 단, $L$-Lipschitz 조건을 넣고 싶다면 무조건 $\mathcal{M} \cap \mathcal{L}_L$ 형태로 operator class를 잡아야 한다
• $\mathcal{Q}$가 위 operator class의 교집합이라면, 단순히 대응되는 조건을 모두 가져오면 된다.
• 즉, 두 점이 operator class의 조건을 만족시키면 무조건 interpolation도 된다는 것이 결론. 점의 개수가 많아지면 성립하지 않는다.
• TMI : monotone operator는 일반적인 경우에서도 maximal monotone operator로 interpolate 할 수 있다 (Zorn's Lemma)

논문의 Theorem 4.1을 직접 검증해보기 위해서, 대응되는 세팅인 $\mathcal{Q}_1 = \mathcal{M}_\mu$, $\mathcal{Q}_2 = \mathcal{M} \cap \mathcal{C}_\beta$를 생각해보자.

• $B$가 지나야 하는 점은 $(z_B, (z-z_B)/\alpha)$와 $(z'_B, (z'-z'_B)/\alpha)$
• 그러니 얻는 식은 $\langle ((z-z')-(z_B - z'_B))/\alpha, z_B - z'_B \rangle \ge \beta ||((z-z')-(z_B - z'_B))/\alpha||^2$
• $A$가 지나야 하는 점은 $(z_A, (2z_B - z-z_A)/\alpha)$와 $(z'_A, (2z'_B-z'-z'_A)/\alpha)$
• 그러니 얻는 식은 $\langle (2(z_B - z'_B) - (z-z') - (z_A - z'_A))/\alpha, z_A- z'_A \rangle \ge \mu ||z_A - z'_A||^2$

추가적으로, $||z-z'||^2 = 1$이라는 조건도 가지고 있다. 눈치챘겠지만, $z-z'$, $z_A-z_A'$, $z_B - z'_B$과 같이 두 변수의 차로 식이 표현된다.

 

이를 치환하고 정리하면, 우리가 원하는 것은 결국 $$\begin{equation*} \begin{aligned} \text{maximize} \quad & ||z - \theta (z_B - z_A)||^2 \\ \text{subject to} \quad & ||z||^2=1 \\ \quad & \langle z-z_B, z_B \rangle \ge (\beta/\alpha) ||z-z_B||^2 \\ \quad & \langle 2z_B - z , z_A \rangle \ge (1+\alpha \mu)||z_A||^2 \end{aligned} \end{equation*}$$를 얻는다. 이제 SDP를 꺼낼 준비가 완료되었다. 마찬가지로 Gram Matrix $$G = \left[ \begin{matrix} \langle z, z \rangle & \langle z_A, z \rangle & \langle z_B, z \rangle \\ \langle z, z_A \rangle & \langle z_A, z_A \rangle & \langle z_B, z_A \rangle \\ \langle z, z_B \rangle & \langle z_A, z_B \rangle & \langle z_B, z_B \rangle \end{matrix} \right]$$를 꺼내자. 작업하고 있는 공간의 차원이 3 이상이라는 가정하에서, 우리가 아는 것은 $G$가 Positive Semidefinite이라는 사실 뿐이다.

 

이제 다음과 같이 행렬을 정의하자. $$ M_O = \left[ \begin{matrix} 1 & \theta & -\theta \\ \theta & \theta^2 & -\theta^2 \\ -\theta & -\theta^2 & \theta^2 \end{matrix} \right], \quad M_I = \left[ \begin{matrix} 1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix} \right]$$ $$ M_\beta^B = \left[ \begin{matrix} -\beta/\alpha & 0 & \beta/\alpha + 1/2 \\ 0 & 0 & 0 \\ \beta/\alpha + 1/2 & 0 & -\beta/\alpha - 1 \end{matrix} \right], \quad M_\mu^A = \left[ \begin{matrix} 0 & -1/2 & 0 \\ -1/2 & -(1+\alpha \mu) & 1 \\ 0 & 1 & 0 \end{matrix} \right]$$ 그러면 최종적으로 우리가 원하는 SDP 형태를 얻는다. $$\begin{equation*} \begin{aligned} \text{maximize} \quad & Tr(M_OG) \\ \text{subject to} \quad & G \succeq 0, Tr(M_IG) = 1 \\ \quad & Tr(M_\mu^A G), Tr(M_\beta^BG) \ge 0 \end{aligned} \end{equation*}$$

 

특히, 이 SDP formulation의 해를 가지고 "worst case"에 대응되는 operator $A, B$를 복원할 수 있다.

$Tr(M_O G)$가 최대가 되는 경우의 $G$를 찾았다면, Gram Matrix의 성질을 이용하여 $z, z_A, z_B$를 복원한 다음 interpolate 하면 끝이다.

 

Part 2 : The Dual Problem and its Interpretations/Usage

이제 얻은 SDP의 dual problem을 생각해보자. 전형적인 계산을 하면 결국 $$\begin{equation*} \begin{aligned} \text{minimize} \quad & \rho^2 \\ \text{subject to} \quad & \lambda_\mu^A, \lambda_\beta^B \ge 0 \\ \quad & S = -M_O - \lambda_\mu^A M_\mu^A - \lambda_\beta^B M_{\beta}^B + \rho^2 M_I \succeq 0 \end{aligned} \end{equation*}$$를 얻는다. 또한, "웬만하면" (regularity condition) Strong Duality가 성립함은 Slater's Condition으로 보일 수 있다.

이는 논문의 정리 3.3.으로, 나름 전형적인 증명이고 테크니컬하므로 생략. 중요한 것은 이 Dual Problem을 어떻게 바라보느냐, 그리고 어떻게 써먹느냐다.

 

눈치를 챘겠지만, notation을 $M_{\mu}^A$, $M_{\beta}^B$로 둔 이유는 사실 이 행렬들, 정확하게는 이 행렬들과 관련된 trace에 대한 조건이 $A$의 $\mu$-strongly monotone, $B$의 $\beta$-cocoercivity를 encode 한 것이기 때문이다. 이와 같이 operator class에 $A, B$가 속하게 되면 이로부터 얻어지는 부등식들이 있고, 우리가 증명할 수 있는 것은 기본적으로 이러한 부등식들의 nonnegative combination이다. 이 생각을 이어가면 결국 얻을 수 있는 결론은

• dual variable $\lambda_\mu^A$, $\lambda_\beta^B$은 $A, B$에 대응되는 부등식들에 대한 가중치이다. (그러니 $0$ 이상이다)
• feasible point에서의 $\rho$ 값은 해당 가중치를 사용하였을 때 얻어지는 contraction factor이며, 이는 optimal 값에 대한 upper bound다.

즉, "가중치를 이렇게 넣었더니 contraction factor가 이렇게 나왔다"는 사실 "dual problem의 feasible point를 찾았다"와 같다.

 

강조하자면, Primal/Dual Problem의 직관적인 의미는 각각

• Primal : 변수로 들어가는 것은 "최악의 경우에 해당하는 operator", 얻어지는 것은 "이런 contraction factor는 기대할 수 없다"는 결론
• Dual : 변수로 들어가는 것은 "증명에 사용될 가중치", 얻어지는 것은 "이런 contraction factor는 얻어질 수 있다"는 결론
• 특히, Duality Gap이 "웬만하면" (Slater's Condition) 0이므로, 정말 아무런 걱정도 할 필요가 없음

 

이제 Dual Problem의 의미를 알았으니, 활용하는 법도 파악할 수가 있다.

• Contraction Factor에 대한 Upper Bound를 확보할 수 있다. 애초에 dual problem에서 항상 나오는 결론이다.
• Dual Problem을 풀면 "증명에 사용될 가중치"를 얻을 수 있다! 그러니 여러 parameter에 대해서 문제를 수치적으로 풀어보고, 이를 통해서 어떤 가중치가 사용되는지 확인한 후, 이에 대한 analytical 공식을 때려맞춘뒤 엄밀한 증명을 시작할 수 (정확하게는, 시도할 수) 있다.
• Convex Optimization에서 수렴성 증명 중 상당 부분은 정말 단순 계산인데, 그 계산각을 재는 게 어렵다. (후에 Acceleration을 다루면 Lyapunov Function에서 또 이 이야기가 나올 것이다) 부등식들을 섞어먹을 가중치를 선정하는 것도 난이도가 상당하다. Dual Problem은 여기서 도움을 준다.