Warm-Starting Iterative Gaussian Processes for Faster Sequential Inference

기술 요약: 더 빠른 순차적 추론을 위한 반복적 가우시안 프로세스의 웜 스타트(Warm-Starting)

문제 정의
가우시안 프로세스(GP)는 회귀, 분류 및 베이지안 최적화를 위한 강력한 비매개변수 모델이지만, 사후 확률(posterior)을 계산하기 위해 공분산 행렬을 역전시키는 데 드는 $O(n^3)$의 비용으로 인해 확장성에 한계가 있다. 그러나 반복적 솔버(예: 켤레 기울기법(Conjugate Gradients), 확률적 경사 하강법(Stochastic Gradient Descent), 교대 투영법(Alternating Projections))는 해를 근사하는 방식을 통해 큐빅 비용을 피하는 방법을 제공하지만, 일반적으로 수렴하기까지 많은 반복이 필요하다. 데이터가 점진적으로 유입되고 사후 확률을 빈번하게 업데이트해야 하는 순차적 환경(예: 능동 학습, 온라인 예측, 베이지안 최적화)에서, 기존의 "콜드 스타트(cold-start)" 방식(모든 가중치를 0으로 초기화하고 이전 계산을 폐기하는 방식)은 병목 현상이 된다. 이러한 비효율성은 동적인 환경에서 반복적 GP의 효능을 제한한다.

방법론
본 논문은 새로운 데이터 포인트로 GP 사후 확률을 업데이트할 때 반복적 선형 솔버를 초기화하기 위한 세 가지 "웜 스타트" 전략을 제안한다. 이 방법들은 이전의 더 작은 선형 시스템의 해($u_1$)를 활용하여 새로운 더 큰 시스템의 가중치($v$)를 초기화함으로써, 처음부터 다시 해결하는 대신 효율성을 높인다.

문제는 기존 데이터(블록 1)와 새로운 데이터(블크 2)를 포함하도록 분할된 행렬 $H$와 벡터 $b$를 포함하는 확장된 선형 시스템 $Hv = b$를 푸는 것으로 프레임화된다. 제안된 세 가지 초기화 방법은 다음과 같다:

1. 나이브 웜 스타트(Naïve Warm-Start): 원래 데이터에 해당하는 가중치($v_1$)를 이전 해($u_1$)로 초기화하고, 새로운 데이터에 대한 가중치($v_2$)는 0으로 초기화한다.
   $$v \leftarrow \begin{bmatrix} u_1 \\ 0 \end{bmatrix}$$
2. 잔차 선 탐색(Residual Line Search): 이 방법은 잔차 방향에 대해 최적의 스칼라 $\alpha$를 결정하기 위해 선 탐색을 수행함으로써 나이브 접근법을 개선한다. 이는 고정된 $v_1 = u_1$에 대해 이차 목적 함수를 최소화한다.
   $$v_2 = \alpha^* r, \quad \text{여기서 } r = b_2 - H_{12}^\top u_1 \text{ 이고 } \alpha^* = \frac{r^\top r}{r^\top H_{22} r}$$
3. 주변 시스템 풀이(Marginal System Solve): 가장 복잡한 이 방법은 주어진 $v_1 = u_1$에 대해 목적 함수를 최소화하는 최적의 $v_2$를 찾기 위해 더 작은 주변 선형 시스템($H_{22}v_2 = r$)을 푼다.
   $$v_2 = H_{22}^{-1} r$$

이론적 분석
저자들은 정확한 해를 $v^*$라고 할 때, 재생 커널 힐베르트 공간(RKHS) 거리 $d^2 = (v - v^*)^\top H (v - v^*)$를 사용하여 이론적 근거를 제공한다. 저자들은 다음을 입증하였다:

• 나이브 웜 스타트는 콜드 스타트와 비교했을 때 RKHS 거리를 엄격하게 감소시킨다 ($d^2_{cold} - d^2_{naïve} \geq 0$).
• 잔차 선 탐색과 주변 시스템 풀이는 이 거리를 더욱 감소시킨다 ($d^2_{naïve} > d^2_{line-search} > d^2_{marginal-solve}$).
• RKHS 거리를 줄이는 것은 선형 시스템의 초기 잔차를 줄이는 것과 동일하며, 이는 수렴에 필요한 반복 횟수와 직접적인 상관관계가 있다.

주요 기여 및 결과
본 논문은 이러한 세 가지 초기화 전략을 도입하고, 회귀 벤치마크 및 베이지안 최적화 작업에 대한 이론적 분석과 경험적 실험을 통해 이를 검증한다.

• 회귀 실험: UCI 저장소의 데이터셋(예: 3droad, protein, buzz)을 사용하여, 수렴까지 필요한 반복 횟수를 콜드 스타트 베이스라인과 비교하였다.

  • 속도 향상: 특정 허용 오차까지 해결할 때, 웜 스타트는 켤레 기울기법(CG)에서 최대 1.4배, 확률적 경사 하강법(SGD)에서 1.5배, 교대 투영법(AP)에서 4.0배의 속도 향상을 달면 달성했다.
  • 극한 사례: AP의 경우, 특히 새로운 데이터와 기존 데이터의 비율이 작을 때 특정 데이터셋에서 최대 19배의 속도 향상을 기록했다.
  • 정확도: 고정된 계산 예산(제한된 반복 횟수) 하에서, 웜 스타트는 더 정확한 사후 확률 추정치를 생성하여 최종 잔차 노름(residual norm)을 줄였다.

• 베이지안 최적화 (병렬 톰슨 샘플링): 고정된 계산 예산을 가진 병렬 톰슨 샘플링 실험에서, 방법들은 목적 함수를 최대화하는 능력을 평가받았다.

  • 성능 이득: 웜 스타트 방법들은 콜드 스타팅과 비교하여 목적 함수에서 찾아낸 최종 최대값을 **CG에서 최대 13%, SGD에서 46%, AP에서 10%**까지 향상시켰다.
  • 누적 진전: 결과는 웜 스타트를 사용할 때 솔버의 진전이 리셋되지 않고 여러 번의 순차적 풀이 과정에서 누적되어, 더 정확한 사후 샘플과 더 나은 최적화 성능을 이끌어냄을 나타냈다.

의의
본 논문은 웜 스타트가 순차적 환경에서 가우시안 프로세스를 확장하기 위한 단순하고 효과적이며 광범위하게 적용 가능한 도구임을 입증한다. 이전의 더 작은 선형 시스템의 해를 활용함으로써, 이 방법들은 정확도를 희생하는 희소 근사(sparse approximation)를 사용하지 않고도 수렴 속도를 실질적으로 높인다. 저자들은 이 접근 방식이 순차적 의사결정 과제에서의 확장성 병목 현상을 직접적으로 해결하여, 동일한 계산 제약 조건 내에서 더 빈번하고 정확한 사후 확률 업데이트를 가능하게 한다고 주장한다. 이 방법들은 기존의 반복적 솔버(CG, SGD, AP)와 결적으로 통합되어 GP 기반 애플리케이션의 효율성을 개선할 수 있는 실용적인 향상책으로 제시된다.