Sharp local sparsity of regularized optimal transport

논문 개요

이 논문은 엔트로피 정규화 (Entropic Regularization) 대신 $L_p$-타입 엔트로피 ($p \in (1, 2]$) 를 사용하여 정규화된 최적 수송 (Regularized Optimal Transport, ROT) 문제를 다룹니다. 최근 ROT 는 계산 효율성과 차원의 저주 회피 능력으로 인해 엔트로피 정규화 최적 수송 (EOT) 의 대안으로 주목받고 있습니다. EOT 와 달리 ROT 는 해의 지지집합 (support) 이 희소 (sparse) 해지는 특성을 가지며, 이 논문은 정규화 파라미터 $\varepsilon \to 0$일 때 이 지지집합이 원래 최적 수송 문제의 지지집합으로 수렴하는 **정확한 수렴 속도 (sharp rate)**를 규명하는 것을 목표로 합니다.

1. 문제 정의 및 배경

• 최적 수송 (OT): 두 확률 측도 $\lambda, \mu$ 사이의 비용 함수 $c(x,y) = \frac{1}{2}\|x-y\|^2$를 최소화하는 결합 (coupling) $\pi$를 찾는 문제.
• 정규화된 최적 수송 (ROT): OT 문제의 목적 함수에 $L_p$ 엔트로피 항을 추가한 문제.
  $$\text{ROT}_{\varepsilon, p} := \inf_{\pi \in \Pi(\lambda, \mu)} \int \frac{1}{2}\|x-y\|^2 d\pi + \varepsilon \int h_p\left(\frac{d\pi}{d(\lambda \otimes \mu)}\right) d(\lambda \otimes \mu)$$
  여기서 $h_p(z) = \frac{|z|^{p-1}}{p-1}$이며, $q = \frac{p}{p-1}$는 켤레 지수입니다.
• 핵심 차이점:
  • EOT: 해의 밀도가 지수 함수 형태이므로 지지집합이 전체 공간으로 퍼져 있음 (maximal support).
  • ROT: 밀도 함수가 $(\cdot)_+^{q-1}$ 형태를 띠므로, 특정 조건에서 밀도가 0 이 되어 지지집합이 좁아짐 (sparse support).
• 연구 질문: $\varepsilon \to 0$일 때, ROT 해의 조건부 측도 $\pi_\varepsilon(\cdot|x)$의 지지집합 $S_x = \{y : \rho_\varepsilon(x, y) > 0\}$의 지름이 얼마나 빠르게 0 으로 수렴하는가?

2. 주요 가정

• $\lambda, \mu$는 컴팩트한 지지집합 $\Omega_0, \Omega_1$을 가지며, $C^{0,\alpha}$ 밀도를 가짐 (유계이고 0 에서 멀어짐).
• 원래 OT 문제의 최적 수송 맵 $T = \nabla \phi$가 $C^{1,\alpha}$ 미분동형사상 (bi-Lipschitz diffeomorphism) 임.
• $\Omega_0, \Omega_1$은 $C^2$ 볼록 영역인 경우 모든 결과가 성립함.

3. 주요 기여 및 결과

이 논문은 경계에서 벗어난 내부 영역 (interior) 에서 다음과 같은 날카로운 국소적 결과를 증명합니다.

3.1. 날카로운 국소 희소성 (Sharp Local Sparsity)

Theorem 3.1은 $\lambda$의 지지집합 내부의 임의의 점 $x$에 대해, 조건부 측도의 지지집합 $S_x$가 반지름이 $\varepsilon^{\frac{1}{d(p-1)+2}}$인 구 (ball) 와 유사하게 행동함을 증명합니다.

• 결과: 내부 영역 $K_0 \Subset \Omega_0$에 대해 충분히 작은 $\varepsilon$에 대하여,
  $$B\left(\nabla \varphi_\varepsilon(x), \frac{1}{R_0}\varepsilon^{\frac{1}{d(p-1)+2}}\right) \subset S_x \subset B\left(\nabla \varphi_\varepsilon(x), R_0\varepsilon^{\frac{1}{d(p-1)+2}}\right)$$
  여기서 $\nabla \varphi_\varepsilon(x)$는 ROT 의 쌍대 변수에서 유도된 볼록 함수의 기울기이며, $R_0$는 $x$와 경계 사이의 거리에 의존하는 상수입니다.
• 의미: 지지집합의 지름이 $\varepsilon^{\frac{1}{d(p-1)+2}}$의 order 로 수렴합니다. 이는 1 차원 데이터나 자기 수송 (self-transport, $\mu=\lambda$) 경우의 기존 결과들을 다변수 (multivariate) 및 일반적인 마진 (marginals) 경우로 일반화한 것입니다.

3.2. 균일한 강한 볼록성 (Uniform Strong Convexity)

Corollary 3.2는 ROT 의 볼록 포텐셜 $\varphi_\varepsilon$이 내부 영역에서 $\varepsilon \to 0$에 대해 균일하게 강한 볼록성 (uniformly strongly convex) 을 가짐을 보입니다.

• 결과: 내부 영역 $K_0$에 대해,
  $$\inf_{\|h\|=1} \langle \nabla^2 \varphi_\varepsilon(x) h, h \rangle \geq \frac{1}{C}$$
  이 성립합니다. 이는 Hessian 행렬의 고유값이 0 으로 수렴하지 않음을 의미하며, 수치적 안정성과 해의 정규성 (regularity) 을 보장합니다.

3.3. ROT 맵의 수렴 속도

Corollary 3.3은 ROT 에 의해 유도된 맵 $\nabla \varphi_\varepsilon$이 원래 OT 맵 $\nabla \phi$로 수렴하는 속도를 제시합니다.

• 결과: $L^2$ 노름에서 수렴 속도는 다음과 같습니다.
  $$\|\nabla \varphi_\varepsilon - \nabla \phi\|_{L^2(K_0)} \leq C \varepsilon^{\frac{1}{d(p-1)+2}}$$
  이는 지지집합의 축소 속도와 직접적으로 연결됩니다.

4. 방법론 및 증명 전략

1. 이중성 (Duality) 활용: ROT 문제의 쌍대 문제 (D-ROT) 를 통해 밀도 함수 $\rho_\varepsilon$의 명시적 형태를 유도하고, 지지집합 $S_x$가 $\xi(x, y) = \langle x, y \rangle - \varphi_\varepsilon(x) - \psi_\varepsilon(y) > 0$인 영역임을 이용합니다.
2. 정규성 추정 (Regularity Estimates): 이전 연구 ([GK26]) 에서 얻은 내부 영역에서의 $\nabla^2 \varphi_\varepsilon$에 대한 균일한 $L^\infty$ 상한을 핵심 도구로 사용합니다.
3. 볼록 분석 (Convex Analysis): Fenchel 부등식과 켤레 함수 (convex conjugate) 의 성질을 사용하여 $\xi(x, y)$의 하한과 상한을 추정합니다.
4. 적분 추정: 지지집합 $S_x$ 위에서 $\xi(x, y)$의 적분 값을 평가하여, 지지집합의 크기가 $\varepsilon$의 특정 거듭제곱에 비례함을 유도합니다.
5. 레이놀즈 수송 정리 (Reynolds' Transport Theorem): $S_x$의 경계가 $x$에 따라 변할 때의 미분 가능성을 다루기 위해 일반화된 수송 정리를 사용하여 2 차 도함수를 계산합니다.

5. 검증 (Explicit Solution)

Section 6에서는 평면 토러스 (flat unit torus) 위의 자기 수송 (self-transport, $\lambda = \mu = \text{Lebesgue}$) 문제에 대해 명시적인 해를 구합니다.

• 이 경우 대칭성에 의해 $\varphi_\varepsilon$이 상수 함수가 되며, 지지집합 $S_x$는 반지름 $R_\varepsilon \approx \varepsilon^{\frac{1}{d(p-1)+2}}$인 구가 됩니다.
• 이 명시적 해를 통해 **Theorem 3.1 에서 유도된 수렴 속도가 날카롭다 (sharp)**는 것을 확인합니다. 즉, 더 빠른 수렴 속도는 불가능합니다.

6. 의의 및 결론

• 이론적 기여: ROT 의 희소성 (sparsity) 이 단순히 "작아진다"는 정성적 사실을 넘어, 정확한 수렴 차수를 규명했습니다. 이는 $p$와 차원 $d$에 따라 수렴 속도가 어떻게 변하는지 정량화했습니다.
• 실용적 의미: ROT 알고리즘의 수렴성 분석, 수치 해석적 안정성 보장, 그리고 희소성 기반의 계산 효율성 (sparse support) 을 이론적으로 뒷받침합니다.
• 확장성: 기존에 1 차원이나 자기 수송 경우에 국한되었던 결과를 일반적인 다변수 확률 측도로 확장했습니다.

요약하자면, 이 논문은 $L_p$ 정규화를 통한 최적 수송 문제에서 해의 지지집합이 $\varepsilon \to 0$일 때 $\varepsilon^{\frac{1}{d(p-1)+2}}$의 속도로 수축하며, 이 과정이 균일한 강한 볼록성과 결합되어 안정적으로 수렴함을 rigorously 증명했습니다.