기술 요약: 고차원 최적 운송을 위한 볼록 완화 접근법

1. 문제 정의

본 논문은 고차원에서 최적 운송(Optimal Transport, OT) 문제를 해결하는 데 내재된 계산적 및 통계적 과제를 다룬다. OT는 기하학적 충실도를 유지하며 확률 분포를 비교하는 강력한 프레임워크이지만, 그 적용은 "차원의 저주"에 의해 제약을 받는다. 구체적으로, 표준 OT 솔버의 계산 비용은 샘플 크기에 따라 급격히 증가하며, 와서스타인 거리(Wasserstein distance)를 추정하는 데 필요한 샘플 복잡도는 차원 $d$에 따라 지수적으로 증가한다. 신경망 파라미터화(비볼록 최적화로 인해 강력한 이론적 보장이 부족함)나 슬라이스 와서스타인 거리(진정한 거리를 복구하지 못하고 근사함)와 같은 기존의 차원 축소 전략들은 연속적인 고차원 분포에 대해 확장 가능하고 이론적으로 근거 있는 해결책을 제공하지 못하는 경우가 많다.

## 2. 방법론

저자들은 고차원 분포 내의 상관관계가 가진 **국소성(locality)**과 **희소성(sparsity)**을 활용하는 볼록 완화(convex relaxation) 접근법의 계열을 제안한다. 이 방법은 전체 결합 운송 계획 $\pi \in \mathcal{P}(X \times Y)$에 대해 최적화를 수행하는 대신, 저차 마진(low-order marginals)과 희소 모멘트 통계량을 사용하여 문제를 근사한다.

2.1 구조적 가정

이 접근법은 $d$차원 좌표를 $K$개의 클러스터로 분할하고, 상관 구조를 인코딩하는 참조 그래프 $G$를 정의하는 것에 의존한다.

• 클러스터 분할: 좌표는 클러스터 $z_k = (x_k, y_k)$로 그룹화된다.
• 참조 그래프: 정점은 클러스터를 나타내고 간선은 쌍별 상호작용을 나타내는 그래프 $G$. 이 방법은 의존성이 그래프 거리와 함께 감소한다고 가정하며, 이를 통해 희소 근사가 가능하다.

2.2 완화 프레임워크

본 논문은 두 가지 주요 수준의 완화를 도입한다.

1. 마진 완화 (Marginal Relaxation):

   • 원래의 OT 문제는 그래프 $G$ 내의 단일 클러스터($\pi_k$) 및 연결된 클러스터 쌍($\pi_{ij}$)에 대응하는 마진에 대해서만 제약을 부과하도록 완화된다.
   • 양의 성질 (Positivity): 전역 측도의 비음성(non-negativity) 제약은 이러한 마진들의 블록 행렬에 대한 양의 준정부호(Positive Semidefinite, PSD) 제약으로 완화된다.
   • 정식화 변형: 저자들은 세 가지 변형을 정의한다:
     • $(OT_{mar})$: PSD 제약과 비음성 제약을 모두 포함 (이중 비음 제약 프로그래밍, Doubly Non-Negative programming).
     • $(OT^1_{mar})$: 전역 PSD 제약을 제거하여 선형 계획법(LP) 문제로 만듦.
     • $(OT^2_{mar})$: 비음성 제약을 제거하여 현수 분해(chordal conversion)를 통해 더 축소 가능한 준정부호 프로그래밍(SDP)으로 만듦.

2. 클러스터 모멘트 완화 (Cluster Moment Relaxation):

   • 공간 이산화 없이 연속 분포를 처리하기 위해, 마진 완화는 합-제곱(Sum-of-Squares, SOS) 모멘트 완화를 사용하여 더욱 근사된다.
   • 측도에 대해 최적화를 수행하는 대신, 변수는 차수 $n$의 다항식 기저로부터 유도된 유한 차원 모멘트 행렬($M_k, M_{ij}$)이 된다.
   • 핵심 혁신: 모든 단항식의 모멘트를 요구하는 표준 SOS 계층(예: Mula and Nouy [44], $O(d^{2n})$ 복잡도)과 달리, 이 방법은 참조 그래프의 국소 클러스터와 간선으로 기저를 제한한다.
   • 복잡도: 결과적인 SDP는 오직 희소한 모멘트 집합만을 포함한다. 클러스터 크기와 완화 차수가 고정되어 있다면, 그래프 $G$의 트리 폭(tree-width)이 유계인 경우 이 문제는 $O(d)$로 스케일링되며, 현수 분해(chordal decomposition)를 통해 해결 가능하다.

2.3 운송 맵 추출 (Transport Map Extraction)

완화된 SDP의 쌍대 변수(dual variables)는 근사된 칸토로비치 포텐셜(Kantorovich potentials)을 제공한다. 선택된 다항식 기저의 스팬(span) 내로 이 포텐셜들을 제한함으로써, 저자들은 해석 가능한 대안인 명시적 운송 맵 $\hat{T}(x) = x - \frac{1}{2}\nabla \hat{f}(x)$를 구축한다. 이는 신경망 기반 생성 모델에 대한 해석 가능한 대안을 제공한다.

3. 주요 기여 및 이론적 결과

3.1 희소 정밀도를 가진 가우시안 모델

가우시안 측도 $\mu = \mathcal{N}(m_1, \Sigma_1)$와 $\nu = \mathcal{N}(m_2, \Sigma_2)$에서 정밀도 행렬이 그래프 $G$에 대해 희소한 경우:

• 지수적 수렴: 저자들은 클러스터 모멘트 완화(특히 차수-1)가 참조 그래프 $G_h$의 연결 반경 $h$가 증가함에 따라 근사 오차에 대해 지수적 수렴 속도를 달성함을 증명한다. 오차 경계는 $C d \rho^{-h}$ 형태이다.
• 개선된 샘플 복잡도: 희소 완화의 통계적 오차 경계는 $O(\sqrt{d/N} + |E(G)|/N)$이다. $|E(G)| = O(d)$인 희소 그래프의 경우, 이는 밀집된 완화 경계인 $O(\sqrt{d/N} + d^2/N)$보다 개선된 것으로, 희소성을 활용하는 것이 필요한 샘플 수를 크게 줄임을 보여준다.

3.2 평균장 측도의 국소 섭동 (Local Perturbations of Mean-Field Measures)

평균장 곱 측도의 국소 섭동인 분포의 경우:

• 근사 경계: 마진 완화가 와서스타인 거리의 선도 차수 기하학(leading-order geometry)을 포착함을 보여주며, 이는 가중 음의 동차 숄베르크(weighted negative homogeneous Sobolev) 노름에 해당한다.
• 통계적 오차: 고정된 완화 차수와 유계된 클러스터 크기 하에서, 통계적 오차는 $O(d N^{-1/2})$로 스케일링되며, 이는 $O(d^2 \epsilon^{-2})$의 샘플 복잡도를 의미한다. 이는 표준 OT 추정에서 발견되는 $d$에 대한 지수적 의존성에 비해 상당한 개선이다.

3.3 일반 통계적 경계

균등 가우시안 꼬리 조건(uniform Gaussian tail conditions)을 만족하는 일반 분포에 대해, 본 논문은 클러스터 모멘트 SDP의 통계적 오차가 주변 차원 $d$가 아니라 로컬 블록 및 그래프 간선의 수($K + |E(G)|$)에 의해 결정됨을 확립한다. 희소 고정 차수 체제에서 오차는 $d$에 선형적으로 스한다.

4. 수치적 결과

광범한 실험을 통해 다양한 설정에서의 이론적 주장을 검증하였다:

• 가우시안 분포: 클러스터 모멘트 완화는 연결 반경 $h$에 대해 지수적 수렴을 보인다. 이는 차원 $d$가 1000까지 증가해도 낮은 상대 오차와 실행 시간을 유지하며, 바닐라 OT 솔버(Sinkhorn) 및 ICNN 베이스라인보다 정확도와 계산 효율성 면에서 우수한 성능을 보인다.
• 비가우시안 곱 측도 (Beta): 이 방법은 비가우시안 곱 측도에 대해서도 높은 정확도(상대 오차 $\approx 10^{-3}$)를 유지하는 반면, 바닐라 OT 솔버는 차원이 높아짐에 따라 급격히 성능이 저하된다.
• 이징 모델 (Ising Models): 이징 모델의 경우, 마진 완화는 정확한 LP 솔루션보다 수십 배 빠른 실행 시간으로 OT 비용에 대한 타이트한 하한을 제공한다.
• 생성 모델링 (Ginzburg-Landau & MNIST): 추출된 운송 맵은 타겟 마진과 일치하는 샘플을 성공적으로 생성한다. Ginzburg-Landau 모델에서 이 방법은 슬라이스 와서스타인 거리에 대해 normalizing flows, ICNN, Sinkhorn 기반 맵보다 우수한 성능을 보인다. MNIST(6D PCA 공간)에서 이 방법은 인식 가능한 숫자 샘플을 생성한다.

5. 의의 및 주장

본 논문은 마진 및 클러스터 모멘트에 기반한 볼록 완화가 고차원 최적 운송을 위한 차원 축소의 유망한 경로를 제공한다고 주장한다.

• 확장성: 국소 구조와 희소성을 활용함으로써, 이 방법은 표준 OT 및 전체 모멘트 계층의 지수적 복잡도를 피하고, 특정 구조적 가정 하에서 차원에 대해 선형적인 스케일링을 달성한다.
• 이론적 보장: 신경망 접근법과 달리, 제안된 방법은 특히 희소 가우시안 및 평균장 섭동 모델에 대해 엄격한 근사 및 통계적 오차 경계를 제공한다.
• 해석 가능성: 이 접근법은 다항식 포텐셜로부터 유도된 명시적 운송 맵을 제공하여, 딥 생성 모델에 대한 더 단순하고 해석 가능한 대안 역할을 한다.
• 강건성: 경험적 결과는 이 방법이 이론적 보장이 덜 명시적인 비가우시안 설정에서도 높은 성능을 유지하며, 전통적인 이산화 기반 방법들이 실패하는 지점에서도 강건함을 보여준다.

저자들은 이러한 완화 방식이 차원의 저주를 효과적으로 완화하여, 구조화된 분포에 대해 고차원 OT를 계산적 및 통계적으로 다룰 수 있게 만든다고 결론짓는다.