Sample complexity of unbalanced entropic OT

기술 요약: 불균형 엔트로피적 최적 운송(Unbalanced Entropic OT)의 샘플 복잡도

문제 정의
최적 운송(Optimal Transport, OT)은 확률 측도를 비교하기 위한 기하학적 프레임워크를 제공하지만, 고전적인 균형 OT(Balanced OT)는 머신러닝 응용 분야에서 두 가지 중요한 한계에 직면한다: (1) 결측되거나 생성된 질량(mass)을 다루기에 부적합한 엄격한 강제 질량 보존 제약 조건, 그리고 (2) 경험적 수렴 속도가 주변 차원(ambient dimension)에 따라 악화되는 불리한 고차원 샘플 복잡도("차원의 저주")이다.

엔트로피 정규화와 불균형 완화($\phi$-발산 사용)가 이러한 문제들을 개별적으로 해결하기 위해 개발되었으나, 불균형 엔트로피적 OT에 대한 기존의 통계적 보증은 주로 스칼라 운송 값(목적 함수)에 국한되어 있다. 최적 결합(optimal coupling, 운송 계획)에 대한 고확률 유한 샘플 경계(high-probability finite-sample bounds)가 부족한 상황이다. 이러한 공백은 생성 모델링이나 궤적 추론과 같은 응로에서, 목적 함수뿐만 아니라 예측 및 보간을 위한 대상인 결합 자체가 매우 중요하기 때문에 결정적이다.

방법론
본 논문은 듀얼 문제의 기하학적 특성에 초점을 맞추어 불균형 엔트로피적 OT의 통계적 분석을 전개한다. 핵심적인 방법론적 혁신은 불균형 설정에서 발생하는 게이지 불변성(gauge invariance)의 상실을 처리하기 위해 이동 불변 포괄(translation-invariant envelope) 정식화를 도입하는 것이다.

1. 듀얼 정식화 및 포괄 구성:
   균형 OT에서는 칸토로비치 포텐셜의 가법적 이동($f \to f+\lambda, g \to g-\lambda$)에 대해 듀얼 목적 함수가 불변이지만, 불균형 OT는 절대적 포텐셜 수준에 의존하는 주변부 발산 페널티로 인해 이 대칭성이 깨진다. 저자들은 이동 불변 포괄 $T_{\alpha, \beta}(f, g) := \inf_{\lambda \in \mathbb{R}} K_{\alpha, \beta}(f+\lambda, g-\lambda)$를 정의한다. 이 구성은 듀얼의 고유한 자유도와 가짜(spurious) 이동 방향을 명시적으로 분리한다.

2. 기하학적 분석 (컴팩트성 및 강볼록성):
   저자들은 완만한 가정(컴팩트 공간, 리프시츠 비용) 하에서 이 포괄 범함수가 소스 측도에 대해 평균이 0이 되도록 포텐셜을 고정하는 컴팩트 앵커 최소화 도메인($P_{\alpha, \beta}^0$)을 가진다는 것을 증명한다. 결정적으로, 이 도메인 위에서 포괄 함수는 가중 $L^2$ 노름에 대해 **균등 강볼록(uniformly strongly convex)**하다. 이를 통해 표준 불균형 듀얼에서 상실되었던 유리한 기하학적 구조를 회복한다.

3. 이동 파라미터 제어:
   포괄 방식은 게이지 고정의 필요성을 제거하지만, 이동 파라미터 $\lambda$에 대한 최적화를 도입한다. 본 논문은 발산 생성기에 대한 완만한 도메인 조건(가정 A2) 하에서 최적의 $\lambda$가 균등하게 유계된 구간 $[-R, R]$ 내에 갇혀 있음을 입증한다. 이를 통해 듀얼 포텐셜에 대한 균등 $L^\infty$ 경계를 얻을 수 있다.

4. 통계적 안정성:
   앵커된 포괄의 강볼록성과 이동 파라미터의 유계성을 활용하여, 저자들은 안정성 추정치를 도출한다. 이들은 경험적 듀얼 포텐셜이 모집단 포텐셜로 균등하게 수렴함을 보여준다. 이러한 듀얼 수렴 속도는 지수 스케일링 관계($d\pi/d(\alpha \otimes \beta) \propto \exp((f \oplus g - c)/\eta)$)를 통해 프라이멀 운송 계획으로 전이된다.

주요 기여

• 이동 불변 듀얼 정식화: 본 논문은 이전에는 Sinkhorn 반복의 알고리즘적 안정성을 위해서만 활용되었던 성질인, 이동 방향을 몫집합(quotienting out)함으로써 불균형 엔트로피적 OT에 대한 강볼록성을 복구하는 엄밀한 듀얼 정식화를 도입한다.
• 계획 수준의 샘플 복잡도: 주요 기여는 단순히 목적 함수 값이 아니라, 불균형 설정에서 최적 결합(운송 계획)에 대한 고확률 유한 샘플 경계를 도출하는 것이다.
• 일반적 발산 적용성: 결과는 $\phi$-발산의 광범위한 클래스(KL, $\chi^2$, 헬링거, 옌센-섀넌, $\alpha$-발산 포함)에 적용되며, 발산별 특정 증명을 요구하지 않고 일반적인 볼록성 및 컴팩트성 논리에 의존한다.
• 명시적 상수: 논문은 이동 파라미터와 그에 따른 샘플 복잡도에 대한 경계에 대한 명시적 상수를 제공하며, 엔트로피 파라미터 $\eta$, 비용 함수, 발산 특성에 대한 의존성을 명확히 한다.

주요 결과
본 논문은 $n$개의 샘플으로부터 유도된 경험적 측도 $\alpha_n, \beta_n$에 대해, 경험적 최적 계획 $\pi_n$과 모집단 계획 $\pi^\star$ 사이의 편차가 다음과 같은 형태의 고확률 경계를 만족함을 입증한다:
$$|\langle h, \pi^\star - \pi_n \rangle| \lesssim C \cdot e^{C(M + \|c\|_\infty)/\eta} \|h\|_\infty \sqrt{\frac{m_\alpha m_\beta (\log n + t)}{n}}$$
여기서 $M$은 듀얼 포텐셜에 대한 균등 상한이고, $h$는 테스트 함수이며, 상수는 문제의 기하학적 구조와 발산 파라미터에 의존한다. 주목할 점은, 샘플링 분포가 주변부의 곱과 일치하는 경우 $\log n$ 인자를 제거할 수 있다는 것이다.

의의 및 주장
본 논문은 이러한 결과가 머신러닝 응용 분야에서 정규화의 실질적인 필요성을 명확히 해준다고 주장한다. 구체적으로:

• 차원 축소 완화: 정규화는 차원의 저주를 완화하여 안정적인 운송 추정에 필요한 샘플 수를 줄여준다.
• 알고리즘 호환성: 도출된 추정치는 확장 가능한 Sinkhorn 유형의 솔버와 호환성을 유지하며, 이는 통계 이론과 계산 실무 사이의 간극을 메운다.
• 역문제에 대한 안정성: 제공된 순방향 안정성 추정치는 관련 연구 [1]에서 언급된 바와 같이, 동반되는 역문제 분석(예: 샘플로부터 비용 회복)에 필수적이다.

저자들은 자신의 분석이 "매우 완만하고 대체로 발산에 무관한 가정"에 의존한다는 점을 강조하며, 이 이론적 프레임워크가 실제 사용되는 표준 모델들에 견고하게 적용될 수 있음을 밝힌다. 저자들은 차원의 저주를 완전히 해결한다고 주장하는 것이 아니라, 고차원 환경에서 엔트로피적 불균형 OT가 비정규화된 와서스타인 거리(Wasserstein distance)에 대한 통계적으로 다룰 수 있는 대안을 어떻게 제공하는지를 입증한다.