Establishing an $\Omega(\sqrt{d})$ complexity lower bound for PDMP samplers and how to break it: a sub-$\sqrt{d}$ algorithm for Gaussian-tailed targets

기술 요약: PDMP 샘플러에 대한 $\Omega(\sqrt{d})$ 복잡도 하한 설정 및 가우시안 꼬리 타겟을 위한 sub-$\sqrt{d}$ 알고리즘

문제 정의
Bouncy Particle Sampler(BPS) 및 Zig-Zag 프로세스와 같은 Piecewise Deterministic Markov Process(PDMP) 샘플러는 전통적인 마르코프 체인 몬테카를로(MCMC) 방법의 대안으로서 비가역적(non-reversible) 특성을 제공한다. 그러나 이러한 이론적 매력에도 불구하고, 기존의 PDMP 샘플러 중 차원 $d$에 대해 $O(\sqrt{d})$보다 나은 계산 복잡도 스케일링을 입증한 것은 없다. 이와 대조적으로, Hamiltonian Monte Carlo(HMC) 및 Metropolis-Adjusted Langevin Algorithm(MALA)과 같은 그래디언트 기반 가역적 방법들은 각각 $O(d^{1/4})$ 및 $O(d^{1/3})$의 우수한 스케일링을 달성한다. 본 연구가 다루는 핵심 질문은 $O(\sqrt{d})$ 장벽이 PDMP 프레임워크의 내재적 한계인지, 아니면 특정 알고리즘 설계의 결과인지 여부이다.

방법론
본 논문은 이론적 하한 증명과 표준 가정을 완화하는 새로운 알고리즘 구축이라는 두 가지 접근 방식을 채택한다.

1. 이론적 하한 (Theoretical Lower Bound):
   저자는 광범위한 클래스의 국소(local) PDMP 샘플러에 대해 $\Omega(\sqrt{d})$ 하한을 설정한다. 증명은 다음과 같은 몇 가지 구조적 가정에 의존한다:

• 타겟 독립성 (Target Independence): 결정론적 흐름(deterministic flow)과 보조 공간(auxiliary space)은 특정 타겟 분포 $\pi$에 의존하지 않는다.
• 국소 점프 (Local Jumps): 점프 커널은 보조 변수는 변경하지만 공간적 위치는 변경하지 않으며, 이를 통해 절대 연속적인 공간 궤적을 보장한다.
• 불변성 (Invariance): 타겟 분포는 이산적인 샘플링 시점뿐만 아니라 모든 연속 시간(continuous time)에서 불변성을 유지해야 한다.

i.i.d. 타겟 분포를 분석함으로써, 증명은 정상 상태 방정식 $L^*\mu = 0$을 만족하기 위해 기대 점프율 $\mathbb{E}[\lambda]$가 $\Omega(\sqrt{d})$로 스케일링되어야 함을 보여준다. 유효하게 독립적인 샘플 간의 거리가 $\sqrt{d}$로 증가함에 따라, 평균 속도가 제한되어 있다면 독립적인 샘플당 필요한 총 점프 횟수는 $\Omega(\sqrt{d})$로 스케일링된다.

2. 알고리즘 혁신 (장벽 돌파):
   이 한계를 극복하기 위해, 본 논문은 타겟 밀도가 모든 연속 시간에서 불변이어야 한다는 가정을 완화하는 새로운 알고리즘을 제안한다. 이는 표준 MCMC와 유사하게 타겟이 이산적인 샘플링 시점에만 불변하도록 허용한다.

• 프레임워크: 이 방법은 Metropolised NUTS-PDMP 프레임워크와 HMC 립프로그(leapfrog) 적분에서 영감을 얻은 새로운 진동 PDMP (Oscillating PDMP) 역학을 통합한다.
• 역학 (Dynamics): 이 프로세스는 고정된 간격이 아닌 무작위 연속 시간 동안 위치 업데이트($\dot{x} = v$)와 속도 업데이트($\dot{v} = -\nabla U(x)$)를 교대로 수행한다.
• 경로 재가중치 부여 (Path Re-weighting): 연속적인 궤적이 타겟 측도를 엄격하게 보존하지 않으므로, 알고리즘은 경로 재샘플링 전략을 사용한다. 이벤트율의 수치적 근사를 사용하여 궤적을 생성한 후, 조건부 확률 밀도에 따라 궤적으로부터 상태를 재샘플링한다. 이 밀도는 경로를 따르는 해밀토니안 변동을 보정하기 위해 상태에 재가중치를 부여하여, 최종 출력이 타겟으로부터의 정확한 샘플이 되도록 보장한다.
• 적응성 (Adaptivity): 알고리즘은 궤적 길이를 적응적으로 결정하기 위해 No-U-Turn(NUTS) 기준을 활용하며, 속도 업데이트를 위한 국소 적응형 단계 크기를 사용하여 가역적 HMC에서 요구되는 복잡한 전역 튜닝 전략을 피한다.

주요 기여

• 복잡도 하한: 본 논문은 표준 PDMP 샘플러가 연속 시간 불변성을 강제할 경우, i.i.d. 타겟에 대해 근본적으로 $\Omega(\sqrt{d})$ 복잡도로 제한된다는 엄격한 증명을 제공한다.
• Sub-$\sqrt{d}$ 알고리즘: 연속 시간 불변성을 포기하는 새로운 Metropolised PDMP 알고리즘을 도입한다. 경로 재가중치 부여와 수치적 근사를 활용함으로써, 가우시안 꼬리 타겟에 대해 $O(d^\alpha)$ (여기서 $\alpha \in [0.2, 0.3]$)의 계산 복잡도를 달성한다.
• 국소 적응성: 제안된 프레임워크는 궤적 길이와 속도 업데이트 사이의 거리 모두에서 국소 적응성을 자연스럽게 통합하며, 이는 복잡한 전략 없이 구현하기 어려운 가역적 HMC의 특징이다.

실험 결과
저자는 다섯 가지 타겟 분포에 대해 차원 $d \in \{2, \dots, 128\}$에 걸친 경험적 스케일링 결과를 제시한다:

• 가우시안 꼬리 타겟: 표준 가우시안, 베이지안 로지스틱 회귀, 가우시안 혼합 모델 타겟에 대해, 유효 샘플 크기(ESS)당 이벤트 수는 $O(d^{0.22})$에서 $O(d^{0.29})$ 사이로 스케일링된다. 그래디언트 계산 횟수는 $O(d^{0.26})$에서 $O(d^{0.31})$ 사이로 스케일링된다. 이러한 결과는 전통적인 PDMP의 $O(\sqrt{d})$ 한계를 크게 상회하며 HMC의 이론적 스케일링에 근접한다.
• 비가우시안 타겟: 알고리즘은 더 두꺼운 꼬리(Logistic) 및 더 얇은 꼬리(Quartic) 분포에 대해서도 강건함을 보여주지만, 증가된 난이도를 반영하여 스케일링 지수가 더 높게 나타난다 ($O(d^{0.43})$ ~ $O(d^{0.64})$).

의의 및 주장
본 논문은 표준 PDMP 프레임워크의 근본적인 한계를 식별했다고 주장한다: 즉, 연속 시간 불변성 요구가 더 나은 차원 스케일링을 가로막는 주요 병목 현상이라는 점이다. 이 제약을 완화함으로써, 저자는 PDMP가 가우시안 꼬리 타겟에 대해 sub-$\sqrt{d}$ 스케일링을 달성할 수 있음을 입증하며, HMC와의 성능 격차를 줄인다. 본 연구는 "sub-$\sqrt{d}$" 성능이 특정 설계의 산물이 아니라, Metropolis-Hastings 재가중치를 통해 보정된 근사적 불변성을 사용하여 작동하는 결과임을 시사한다. 저자는 표준 PDMP에 대한 이론적 하한이 확립되었지만, 제안된 알고리즘이 비가역적 PDMP의 이점을 유지하면서도 고차원 효율성을 위한 실질적인 경로를 제공한다고 결론짓는다.