Convex Relaxations for the Optimization of Markov Processes

기술 요약: 마르코프 과정의 최적화를 위한 볼록 완화 (Convex Relaxations)

문제 정의
본 논문은 주어진 두 확률 분포 $\mu$와 $\nu$ 사이를 보간하는 마르코프 과정을 최적화하면서 누적 비용을 최소화하는 문제를 다룬다. 이 과정은 중간 법칙(laws)들의 수열 $\{\rho_s\}_{s=0}^T$와 마르코프 전이 커널(transition kernels) $\{K_s\}_{s=0}^{T-1}$로 정의된다. 목적 함수는 다음과 같은 일보 비용(one-step costs)의 합을 최소화하는 것이다:
$$\inf \sum_{s=0}^{T-1} \int_{\Omega} \int_{\Omega} c_s(x, y) K_s(x, dy) d\rho_s(x)$$
단, 초기 및 종단 제약 조건($\rho_0 = \mu, \rho_T = \nu$)과 마르코프 진화 제약 조건($\rho_{s+1} = (K_s)_* \rho_s$)을 만족해야 한다.

주요 계산상의 난제는 **차원의 저주(curse of dimensionality)**이다. 고차원 상태 공간에서는 연속적인 상태들의 전체 결합 분포(joint distribution, 즉 결합 $\pi_s$)를 표현하는 것이 불가능하다. 본 논문은 허용 가능한 전이 커널이 특정 제약 조건(예: 서포트 제약, 국소 업데이트 규칙)을 만족하고, 비용 함수가 국소적 분해(local decomposition)를 허용하는 설정에 집중한다.

방법론
저자들은 국소성(locality)과 희소한 상호작용 구조(sparse interaction structures)를 활용하는 순차적 결합 정식화(sequential-coupling formulations) 및 볼록 완화(convex relaxations) 기반의 프레임워크를 제안한다.

1. 순차적 결합 정식화 (Sequential-Coupling Reformulation):
   전이 커널을 최적화하는 문제를 순차적인 결합 $\pi_s(dx, dy) = \rho_s(dx)K_s(x, dy)$들을 최적화하는 문제로 재정식화한다. 제약 조건들은 이 결합들의 주변 분포(marginals)에 관한 식으로 다시 쓰인다. 중간 분포들은 결합 안으로 흡수되며, 여기서 $\rho_{s+1}$은 $\pi_s$의 우측 주변 분포이자 $\pi_{s+1}$의 좌측 주변 분포가 된다.

2. 볼록 완화 (Convex Relaxations):
   전체 결합 $\pi_s$를 표현하는 것을 피하기 위해, 저자들은 오직 저차원의 국소 정보만을 유지하는 두 가지 유형의 볼록 완화를 개발한다.

   • 주변부 완화 (Marginal Relaxation): 전체 결합을 클러스터 그래프 $\mathcal{G} = (\mathcal{C}, \mathcal{E})$에 정의된 클러스터 및 클러스터 쌍에 대한 국소 주변부로 대체한다. 이 완화는 다음을 강제한다:
     • 클러스터와 클러스터 쌍 간의 주변부 일관성(consistency).
     • 시간 단계 간의 질량 보존(mass conservation, 유지된 클러스터 쌍에 투영됨).
     • 국소 양의 성(positivity) 및 전역 양의 성(global positivity) 제약 (후자는 국소 주변부가 전역적인 비음의 측도로 확장될 수 있음을 보장하며, 흔히 모멘트 유사 행렬에 대한 양의 준정부호(PSD) 제로를 통해 수행됨).
     • 국소 주변부로 투영된 허용 가능성(admissibility) 제약.
   • 클러스터 모멘트 완화 (Cluster Moment Relaxation): 전체 주변부 대신, 클러스터 상의 기저 함수(예: 단항식)에 대한 유한한 모멘트 집합을 사용한다. 이는 연속적인 상태 공간에 적합하다. 결정 변수는 모멘트 행렬이다. 제약 조건에는 모멘트 일관성, 질량 보존, 그리고 전역 양의 성(조립된 모멘트 행렬에 대한 PSD 제약)이 포함된다.

두 프레임워크 모두 볼록 최적화 문제(유한 상태의 경우 아핀 제약을 가진 선형 계획법(LP), 또는 연속 상태나 일반적인 제약의 경우 준정부호 계획법(SDP))로 귀결된다. 이는 원래 문제에 대한 계산 가능한 하한(lower bounds)을 제공하며, 중간 분포의 저차 통계량을 복구한다.

3. 역학의 복구 (Recovery of Dynamics):
   • 동적 최적 운송 (Benamô–Brenier): 상태 공간이 볼목하고 비용이 운동 에너지($\|x-y\|^2$)이며 커널 제약이 없는 경우, 이 문제는 베남-브레니에(Benamô–Brenier) 측지선을 복구한다. 저자들은 완화된 문제의 쌍대 변수(dual variables)가 베남-브레니에 문제의 쌍대 포텐셜(dual potentials)을 근사함을 보여준다. 이 포텐셜들을 미분함으로써 근사적인 속도장(velocity field)을 복구할 수 있으며, 이는 흐름(flow)과 그에 대응하는 마르코프 커널을 유도한다.
   • 일반 제약 프로세스: 일반적인 제약(예: 이징 모델의 단일 스핀 업데이트)의 경우, 복구된 국소 통계량에 파라미터 가족(예: 글라우버 역학)을 적합시킨다(fitting). 이는 예측된 다음 단계의 주변부(파라미터 커널을 통해 얻은)와 완화로부터 복구된 주변부 사이의 제곱 오차를 최소화하는 방식으로 이루어진다.

주요 기여

• 정식화: 본 논문은 마르코프 과정 최적화를 순차적 결합 정식화로 재구성하며, 전체 결합 분포 대신 희소한 국소 정보(주변부 또는 모멘트)를 활용하여 고차원으로 확장 가능한 볼록 완화 프레임워크를 제안한다.
• 동적 최적 운송과의 연결: 동적 최적 운송이 이 프레임워크의 특수한 경우임을 입증한다. 결정적으로, 완화된 해로부터 근저에 있는 베남-브레니에 속도장을 복구하는 절차를 제공하여, 정적 완화와 동적 흐름 사이의 간극을 메운다.
• 제약된 역학으로의 일반화: 이 프레임워크는 단순한 운송을 넘어 일반적인 제약이 있는 마르코프 과정을 다룰 수 있도록 확장된다. 저자들은 이징 모델 사이의 운송에 글라우버 역학을 적합시켜, 복구된 국소 통계량을 실행 가능한 마르코프 커널로 변환하는 과정을 통해 이를 설명한다.

결과
논문은 접근법을 검증하는 수치 실험을 제시한다:

• 가우시안 운송: 50차원 가우시안 설정에서, 모멘트 완화는 중간 평균, 공분산 및 아핀 속도장을 정확하게 복구한다. 이 방법은 (SDP를 통해 몇 초 내에 해결되어) 계산 효율적이며, 궤적을 따른 공분산 오차 측면에서 입자 기반 역전파(back-propagation) 방법보다 더 정확한 것으로 나타났다.
• 긴즈부르크-란다우(Ginzburg–Landau) 운송: 가우시안 분포를 10차원의 비가우시안 긴즈부르크-란다우 분포로 성공적으로 운송한다. 복구된 모멘트로부터의 최대 엔트로피 재구성은 국소적 및 장거리 상관관계를 포함한 분포의 점진적인 변형을 포착한다.
• 이징 모델: 제약된 운송(강자성 및 반강자성 이징 모델 간의 1D 및 2D)을 처리한다. 주변부 완화(LP로 해결됨)는 국소 스핀 주변부를 복구하며, 이는 다시 시변(time-inhomogeneous) 글라우버 역학을 적합하는 데 사용된다. 적합된 역학은 복구된 주변부를 성공적으로 재현하고 유효한 샘플 궤적을 생성한다.

의의 및 주장
본 논문은 자신의 프레임워크가 전체 상태 표현의 지수적 비용을 피함으로써 고차원 마르코프 과정 최적화에 대한 실행 가능한 대안을 제공한다고 주장한다. 이 프레 framework는 다음을 제공한다:

1. 계산 가능한 하한: 완화는 최적 비용에 대한 엄격한 하한을 제공한다.
2. 복구 가능한 통계량: 저차 통계량(평균, 공분산, 모멘트)을 복구한다.
3. 동적 재구성: 정적 운송 방법과 달리, 이 프레임워크는 완화된 해로부터 근저의 역학(속도장 또는 전이 커널)을 재구성할 수 있게 한다.
4. 다재다능함: 동적 최적 운송과 제약된 확률 제어(글라우버 역학 등)를 하나의 볼록 최적화 체계 아래 통합하며, 이산 및 연속 상태 공간 모두에 적용 가능하다.

저자들은 이 방법이 국소 통계량과 근사적 역학을 복구하지만, 중간 분포의 국소성을 정확하게 보존하는 문제는 여전히 이론적인 미해결 과제로 남아 있으며, 현재 프레임워크가 특정 유형의 제약과 비용 구조로 제한되어 있다는 점을 겸허히 언급한다.