Stability of the Monge Map in Semi-Dual Optimal Transport

기술 요약: 반이중 최적 수송에서 몽주 사상의 안정성

문제 제기
최적 수송 (Optimal Transport, OT) 은 GAN, VAE, 확산 모델과 같은 생성 모델의 기반이 되어 기계 학습에서 핵심적인 도구로 자리 잡았습니다. 신경망 최적 수송 (Neural Optimal Transport, NOT) 을 포함한 상당수의 알고리즘은 OT 문제의 반이중 (semi-dual) 형식과 상각 최적화 (amortized optimization) 에 의존합니다. 이러한 방법들은 특정 조건 하에서 최적 수송 사상 (몽주 사상) 의 존재성과 유일성을 활용하지만, 학습된 사상에 대한 엄격한 수렴 보장을 종종 결여하고 있습니다. 기존 문헌은 종종 최적 사상의 존재와 최적화 문제의 잘-제정됨 (well-posedness) 을 가정하지만, 이러한 가정은 실제 적용 시 실패할 수 있습니다. 또한, 실증적 관찰에 따르면 수치 알고리즘은 쌍대 포텐셜 ($\psi$) 을 업데이트하는 것보다 수송 사상 ($t$) 을 업데이트하는 데 훨씬 더 많은 반복 횟수가 필요한 경향이 있으며, 이는 이전까지 이론적 설명이 부재했던 현상이었습니다.

방법론 및 이론적 프레임워크
저자들은 OT 문제의 반이중 형식을 분석하며, 특히 목적 함수의 안장점 (saddle-point) 구조에 초점을 맞춥니다. 본 연구는 $X$와 $Y$가 르베그 측도에 대해 절대연속인 확률 측도 $\mu$와 $\nu$를 가진 $\mathbb{R}^n$의 콤팩트 부분집합이라고 가정합니다.

1. 안장점 분석: 본 논문은 수송 사상 $t$와 포텐셜 $\psi$를 포함하는 미니맥스 문제로 반이중 문제를 재형식화합니다. 목적 함수는 다음과 같이 정의됩니다:
   $$F(\psi, t) = \int_X c(x, t(x)) d\mu + \int_Y \psi(y) d(\nu - t_\sharp \mu)$$
   저자들은 이 형식이 퇴화한 안장점 구조를 가짐을 보여줍니다. 구체적으로, 최적 수송 사상 $T^\star$에서 함수 $F(\psi, T^\star)$의 값은 포텐셜 $\psi$에 의존하지 않게 됩니다. 이 "평탄함"은 수송 사상이 최적에 근접하면, 사상이 아직 완벽하게 최적이지 않더라도 포텐셜 $\psi$가 목적 함수에 의해 더 이상 유일하게 결정되지 않음을 의미합니다.

2. 수렴 조건: 이전 연구들이 사상의 수렴을 증명하기 위해 쌍대 포텐셜의 최적성에 의존했던 것과 달리, 본 논문은 $\psi$가 최적일 필요가 없는 몽주 사상의 수렴에 대한 필요충분조건을 유도합니다. 저자들은 $L^2$ 노름에서 수송 사상 $t$에 대한 오차 상계를 확립합니다:
   $$\|t - T^\star\|_{L^2}^2 \lesssim |F(t, \psi) - W_2(\mu, \nu)^2| + d_{KR}(t_\sharp \mu, \nu)$$
   이 추정은 최적 사상까지의 거리가 목적 함수 값의 차이와 푸시포워드 측도와 목표 측도 간의 칸토로비치 - 루빈슈타인 거리에 의존함을 보여주며, $\psi$가 최적 포텐셜에 근접하는지 여부와는 무관합니다.

3. 동역학 시스템 해석: 본 논문은 NOT 알고리즘의 학습 동역학을 연속 시간 2-시간 척도 동역학 시스템으로 해석합니다. 분석 결과, 중간 학습 단계에서는 제약 조건 $t_\sharp \mu = \nu$가 만족되지 않아 복원력이 없으면 $\psi$에 대한 최대화가 무계 (unbounded) 가 됨을 밝힙니다. 시스템을 안정화시키기 위해, 원변수 $t$는 쌍대 변수 $\psi$보다 더 빠른 시간 척도로 진화해야 합니다. 이는 포텐셜에 대한 단일 경사 상승 단계마다 수송 사상에 대해 여러 번의 경사 하강 단계를 수행하는 실증적 관행에 대한 이론적 근거를 제공합니다.

주요 기여 및 결과

• 퇴화성 식별: 본 논문은 반이중 OT 형식화에서 목적 함수가 최적 사상에서 포텐셜과 무관해지는 퇴화한 안장점 구조를 명시적으로 식별합니다. 이는 수송 사상이 수렴함에도 불구하고 포텐셜이 발산하거나 수렴하지 못할 수 있는 이유를 설명합니다.
• 포텐셜과 무관한 수렴 추정: 저자들은 쌍대 포텐셜의 최적성을 가정하지 않고 수송 사상의 오차를 상한하는 수렴 추정식 (식 17) 을 제공합니다. 이는 사상 수렴을 포텐셜 수렴과 직접적으로 연결했던 기존 문헌의 가정에 도전합니다.
• 2-시간 척도 업데이트에 대한 설명: 본 논문은 NOT 및 관련 WGAN 형식화에서 사용되는 "2-시간 척도" 업데이트 규칙을 이론적으로 검증합니다. 포텐셜이 업데이트되기 전에 제약 위반을 줄이고 시스템을 안정화시키기 위해 포텐셜 업데이트당 수송 사상 $t$를 여러 번 업데이트 ($K \eta_t / \eta_\psi$) 하는 것이 필수적임을 보여줍니다.
• 실험적 검증: 가우스 분포에 대한 수치 실험은 포텐셜이 최적에서 멀리 떨어져 있음에도 불구하고 수송 사상이 최적 해에 수렴할 수 있음을 확인합니다. 결과는 업데이트 단계의 비율 ($K$) 과 학습률 ($\eta_t/\eta_\psi$) 이 사상과 포텐셜 중 어느 것이 더 정확하게 학습되는지에 결정적인 영향을 미친다는 것을 보여줍니다.

의의 및 주장
본 논문은 신경망 최적 수송 알고리즘의 실제 동작, 특히 왜 사상에 대해 포텐셜보다 더 많은 반복이 필요한지에 대한 이론적 설명을 제공한다고 주장합니다. 반이중 문제를 퇴화한 안장점을 가진 제약 최적화 작업으로 특성화함으로써, 저자들은 포텐셜 최적성에 기반한 표준 수렴 보장이 불충분한 이유를 명확히 합니다.

저자들은 반이중 문제에서 하한 (infimum) 의 존재가 포텐셜의 최소화자 (minimizer) 의 존재를 보장하지 않는다는 점을 강조하며, 이는 기존 문헌에서 잘못된 주장을 초래해 왔다고 지적합니다. 그들은 "가짜 해 (spurious solutions)"와 실제에서 관찰되는 경사 편차가 이 퇴화성에서 비롯된다고 주장합니다. 즉, 최적 사상 근처에서 서로 다른 포텐셜들이 서로 다른 경사를 생성한다는 것입니다. 따라서 본 논문은 포텐셜에 구조적 제약 (예: 볼록성) 을 부과하면 퇴화성을 줄일 수 있지만 근사 편차를 도입하게 되며, 반면 제약이 없는 매개변수화는 엄격한 안장점 속성이 없더라도 더 잘 수행될 수 있다고 제안합니다.

이 연구는 반이중 OT 에서 몽주 사상의 안정성이 사상과 포텐셜 업데이트의 상대적 시간 척도에 달려 있으며, 사상의 수렴이 포텐셜의 수렴을 의미하지는 않는다고 결론지었습니다.