Inversion-Free Natural Gradient Descent on Riemannian Manifolds

1. 연구 배경 및 문제 정의 (Problem)

• 자연 경사법 (Natural Gradient Descent, NGD): 통계적 최적화에서 널리 사용되며, 피셔 정보 행렬 (Fisher Information Matrix, FIM) 의 역행렬을 사용하여 매개변수 공간의 기하학적 구조를 반영한 최적화 방향을 제공합니다. 이는 매개변수화 불변성 (parameterization-invariant) 을 가지며 수렴 속도를 개선합니다.
• 기존 방법의 한계:
  • 대부분의 기존 연구는 매개변수 공간이 유클리드 공간 (Euclidean space) 이라고 가정합니다.
  • 실제 통계 및 머신러닝 문제 (SPD 행렬, Stiefel 다양체, Grassmann 다양체 등) 는 제약 조건이 있어 리만 다양체 구조를 가집니다.
  • 기존 리만 다양체 기반 NGD 는 FIM 의 역행렬을 직접 계산해야 하므로, 고차원 문제에서 계산 비용이 $O(d^3)$으로 매우 비싸고 수치적 불안정성이 발생할 수 있습니다.
  • 또한, 일부 방법은 임베딩 공간 (ambient space) 에 의존하여 내재적 (intrinsic) 인 기하학적 구조를 완전히 활용하지 못합니다.
• 목표: 리만 다양체 위에서 FIM 의 역행렬을 명시적으로 계산하지 않고 (Inversion-Free), 온라인으로 근사하며 수렴성을 보장하는 확률적 자연 경사법을 개발하는 것.

2. 제안된 방법론 (Methodology)

저자들은 Sherman-Morrison 공식을 활용하여 FIM 역행렬의 온라인 근사를 유지하는 알고리즘을 제안했습니다.

핵심 아이디어

1. 내재적 (Intrinsic) 접근: 임베딩 공간에 의존하지 않고, 다양체 위의 접공간 (Tangent space) 에서만 연산을 수행합니다.
2. 역행렬이 없는 업데이트:
   • 각 반복 단계에서 샘플링된 **스코어 벡터 (Score vector, $\nabla \log q_\theta(y)$)**를 사용하여 FIM 근사 행렬 $H_s$를 업데이트합니다.
   • Sherman-Morrison 공식을 사용하여 $H_s$의 역행렬 $H_s^{-1}$을 $O(d^2)$의 비용으로 업데이트합니다 (역행렬 계산인 $O(d^3)$을 피함).
3. 벡터 수송 (Vector Transport) 의 활용:
   • 리만 다양체에서는 각 반복점 $\theta^{(s)}$의 접공간 $T_{\theta^{(s)}}M$이 다릅니다. 따라서 이전 단계의 역행렬 근사 $H_s^{-1}$을 현재 단계의 접공간으로 이동시키기 위해 벡터 수송 (Vector Transport) 연산이 필수적입니다.
   • 알고리즘은 $H_s^{-1}$을 수송한 후, 새로운 스코어 벡터로 업데이트하고, 이를 통해 자연 경사 방향을 계산하여 리트랙션 (Retraction) 을 통해 다음 매개변수로 이동합니다.
4. 제한된 메모리 변형 (Limited-memory Variant):
   • 고차원 문제에서 $d \times d$ 행렬을 저장하는 것이 불가능할 경우, 최근 $K$개의 스코어 벡터만을 사용하여 저랭크 (low-rank) 근사를 수행하는 변형 알고리즘을 제안했습니다. 이는 저장 공간을 $O(dK)$로 줄여줍니다.

알고리즘 흐름 (Algorithm 1)

1. 수송: 이전 단계의 역행렬 근사 $H_s^{-1}$을 현재 접공간으로 수송 ($T_{s, s-1}$).
2. 샘플링: 현재 분포 $q_{\theta^{(s)}}$에서 데이터 $y$를 샘플링하고 스코어 벡터 $\phi_{s+1}$을 계산.
3. 업데이트: Sherman-Morrison 공식을 사용하여 $H_{s+1}^{-1}$ 업데이트.
4. 자연 경사 단계: $v_{s+1} = -\tau_{s+1} H_{s+1}^{-1} \widehat{\nabla} L(\theta^{(s)})$ 계산.
5. 리트랙션: $\theta^{(s+1)} = R_{\theta^{(s)}}(v_{s+1})$.

3. 주요 기여 (Key Contributions)

1. 리만 다양체용 역행렬이 없는 자연 경사법 제안:
   • 기존 유클리드 공간에서의 방법론 (Godichon-Baggioni et al., 2024) 을 리만 다양체로 일반화했습니다.
   • 내재적 (Intrinsic) 인 정의를 사용하여 임베딩 공간이 필요 없으며, 표준적인 다양체 및 목적 함수의 정칙성 가정만 요구합니다.
2. 강력한 수렴성 증명 (Convergence Analysis):
   • 거의 확실한 수렴 (Almost-sure convergence): 매개변수 반복열이 국소 최적점까지 거의 확실하게 수렴함을 증명했습니다.
   • 수렴 속도: 단계 크기 (step size) 지수 $\alpha > 2/3$일 때, 최적점까지의 거리의 제곱에 대해 $O(\frac{\log s}{s^\alpha})$의 수렴 속도를 증명했습니다.
   • FIM 근사의 점근적 정확성: 수송 (transport) 에 의한 오차와 홀로노미 (holonomy, 곡률로 인한 오차) 가 누적되더라도, 제안된 근사 FIM 이 실제 FIM 으로 거의 확실하게 수렴함을 보였습니다.
3. 저장 공간 효율성:
   • 제한된 메모리 변형을 통해 저장 복잡도를 2 차 (quadratic) 에서 2 차 미만 (sub-quadratic) 으로 낮췄습니다.
4. 실험적 검증:
   • 가우시안 변분 추론 (Gaussian Variational Inference): Bures-Wasserstein 다양체 (공분산 행렬의 기하학) 에서 유클리드 기반 방법 및 정확한 자연 경사법과 비교하여 우수한 성능을 입증했습니다.
   • 정규화 흐름 (Normalizing Flows) on Stiefel Manifold: 직교 제약 조건이 있는 Stiefel 다양체 위에서 변분 추론을 수행하여 유효성을 검증했습니다.

4. 실험 결과 (Results)

• 가우시안 변분 추론 (Bayesian Logistic Regression):
  • 데이터셋: Ionosphere, Breast Cancer, Sonar, Adult, Mushrooms 등.
  • 비교: 유클리드 기하 (Euc) vs Bures-Wasserstein 기하 (BW), 그리고 정확한 NGD vs 제안된 근사 NGD.
  • 결과:
    • Bures-Wasserstein 다양체를 사용한 방법 (BW-NGD) 이 유클리드 기반 방법보다 더 빠르고 안정적으로 수렴했습니다. 특히 고차원 데이터셋에서 유클리드 근사법은 불안정하여 작은 학습률을 요구했으나, BW 기반 방법은 큰 학습률에서도 안정적이었습니다.
    • 제안된 "역행렬이 없는 (Approx)" 방법이 "정확한 (Exact)" 자연 경사법과 유사한 성능을 내면서도 계산 효율성이 뛰어났습니다.
• Stiefel 다양체 (Normalizing Flows):
  • Sylvester Normalizing Flows 를 사용하여 Stiefel 다양체 위에서 변분 추론을 수행했습니다.
  • 제안된 리만 자연 경사법이 Riemannian SGD 및 외재적 (Extrinsic) 자연 경사법보다 더 낮은 ELBO (Evidence Lower Bound) 값을 달성하여 더 나은 최적화 성능을 보였습니다.

5. 의의 및 결론 (Significance)

이 논문은 통계적 최적화 분야에서 기하학적 구조를 올바르게 반영하면서도 계산적으로 효율적인 알고리즘을 제공한다는 점에서 중요한 의의를 가집니다.

• 이론적 기여: 리만 다양체 상의 확률적 자연 경사법에 대한 엄격한 수렴성 분석을 제공하며, 벡터 수송과 곡률 오차가 수렴 속도에 미치는 영향을 정량화했습니다.
• 실용적 기여: 양정치 행렬 (SPD), 직교 행렬, 고정 랭크 행렬 등 제약 조건이 있는 복잡한 매개변수 공간에서 자연 경사법을 적용할 수 있는 실용적인 프레임워크를 제시했습니다.
• 확장 가능성: 이 방법은 유한 차원 모델을 넘어, Wasserstein 공간과 같은 무한 차원 확률 측도 공간으로의 확장 가능성을 시사합니다 (예: SVGD 등).

요약하자면, 이 연구는 리만 기하학의 이점 (제약 조건 자동 준수, 수렴성 보장 등) 을 유지하면서, 자연 경사법의 계산적 병목 현상 (역행렬 계산) 을 해결한 획기적인 접근법입니다.