기술 요약: 가속화된 대칭 비음수 행렬 분해를 통한 저계수 의존성 분해

문제 정의

대칭 비음수 행렬 분해(Symmetric Non-negative Matrix Factorization, SymNMF)는 대칭적이고 원소별로 비음수인 의존성 행렬 $S \in \mathbb{R}^{n \times n}_+$를 저계수 인자 $H \in \mathbb{R}^{n \times k}_+$ (여기서 $k \ll n$)로 분해하는 것을 목표로 한다($S \approx HH^\top$). 이 분해는 구성원들이 공통된 의존성 패턴을 공유하는 잠재적 그룹 구조를 드러내며, 소프트 클러스터링(soft clustering)과 학습된 임베딩(learned embeddings)의 역할을 수행한다.

본 논문은 SymNMF의 확장성 격차 문제를 다룬다. 이 방법론은 잘 확립되어 있으나, 대규모 포트폴리오(수천 개에서 수백만 개의 금융 상품)에 대한 실제 적용은 다음의 이유로 제약을 받아왔다:

1. 메모리 제약: 표준 목적 함수 정식화는 명시적인 $n \times n$ 중간 행렬을 요구하며, 이로 인해 이전 연구들은 중규모 크기($n \lesssim 10^4$)에 국한되었다.
2. 체계적 비교 부족: 현실적이고 통제된 기저 사실(ground-truth) 입력을 바탕으로 솔버 제품군(solver families)에 대한 종합적인 평가가 이루어지지 않았다.
3. 최적화 과제: 중규모에서는 효과적인 방법들이 긴 실행 시간이 필요한 대규모 $n$에서는 실패하는 경우가 많으며, 이는 특히 제약 조건 처리(투영 vs. 재매개변수화)와 적응형 옵티마이저 메모리 간의 상호작용 때문에 발생한다.

본 연구는 금융 리스크 요인을 나타내는 두 가지 특정 입력 유형에 집중한다:

• 절대 피어슨 상관 계수 행렬(Absolute Pearson Correlation Matrices): 전체 분포에 걸친 의존성을 포착한다.
• 꼬리 쌍별 의존성 행렬(Tail Pairwise Dependence Matrices, TPDM): 극단값 이론(Extreme Value Theory)에 근거하여, 극단적인 사건 발생 시의 조건부 의존성을 포착한다. 이러한 행렬은 종종 단일 공통 요인에 의해 지배되는 "평탄하고" 조건수가 나쁜(ill-conditioned) 스펙트럼을 보인다.

방법론

1. 메모리 효율적 재정식화

$n \approx 10^6$까지 확장할 수 있도록, 저자들은 트레이스 항등식(trace identity)을 사용하여 목적 함수를 재정식화하였다. 표준 프로베니우스 노름 $\|S - HH^\top\|_F^2$은 다음과 같이 확장된다:
$$\|S\|_F^2 - 2 \text{tr}(H^\top SH) + \|H^\top H\|_F^2$$
이를 통해 $n \times n$ 잔차 행렬 $S - HH^\top$을 생성할 필요가 없어진다. 모든 중간 단계는 $n \times k$ 또는 $k \times k$ 행렬으로 축소된다. 이러한 대수적 변화는 단일 GPU에서의 최대 가능 $n$을 (FP32 기준 약 60,000에서 약 130,000으로) 거의 두 배로 늘리며, $n = 10^6$을 위한 멀티 노드 분산을 가능하게 한다.

2. 솔버 제품군 및 구성

본 연구는 세 가지 패러다임에 걸쳐 7개의 알고리즘 제품군(30개 이상의 구성)을 평가한다:

• 경사 투영(Gradient Projection): 투영 경사 하강법(PGD), 가속 근접 경사법(APG/FISTA).
• 적응형 1차 방법(Adaptive First-Order): AdaGrad, RMSprop, Adam, NAdam, Adan, 그리고 본 연구에서 도입된 세 가지 새로운 확장형:
  • Piecewise AdaGrad: 목적 함수의 정체(stagnation) 발생 시 누적기(accumulator)를 리셋하여 포화(saturation)를 방지한다.
  • Row-Stochastic SVRG: 주기적인 전체 그래디언트 스냅샷과 행 서브샘플링을 결합하여 균일한 누적기 성장을 유지한다.
  • Block-SVRG AdaptGrow: 밀집 블록 샘플링과 적응형 배치 성장을 사용하며(작게 시작하여 정체 시 전체 배치로 성장), SVRG 하이브리드 스냅샷을 사용하여 행별 누적기 이질성을 교정한다.
• 분할/미러 디센트(Splitting/Mirror Descent): 다중 업데이트(MU), ADMM, 블록 좌표 하강법(HALS, ANLS), 그리고 딥 언폴딩(Deep Unfolding, SymNMF-Net).

3. 제약 조건 처리

본 논문은 $H \ge 0$을 강제하기 위한 두 가지 전략을 비교한다:

• 투영 공간(Projected Space): 업데이트 후 $H$를 직접 클램핑(clamping)한다.
• Softplus 재매개변수화(LogSpace): $H = \text{softplus}(\Theta)$인 무제약 $\Theta$를 최적화한다.
  저자들은 Softplus가 소규모에서는 단기 메모리 옵티마이저(예: RMSprop)와 2차 방법론에 도움이 되지만, 체인 룰(chain-rule) 그래디언트의 비정상성(non-stationary nature)으로 인해 실행 시간이 길어짐에 따라 장기 메모리 누적기(예: AdaGrad, Adam)를 손상시킨다는 것을 발견했다. 따라서 대규모 실험에서는 투영 공간을 사용한다.

4. 수렴 기준

엄격한 3단계 정지 규칙이 균일하게 적용된다:

1. Loss Gate: 정규화된 제곱 오차 $E_t < 0.1$.
2. KKT 조건: 엔트리 정규화된 투영 그래디언트 노름 $\|\nabla_{\text{proj}} f(H)\|_F / (nk) < \tau_g$.
3. 정체(Stagnation): 상대적 목적 함수 개선도가 임계값 미만일 때.
   이는 솔루션이 단순히 낮은 손실을 갖는 것뿐만 아니라 정지점(stationary point)임을 보장하여, 평탄한 골짜기(flat valleys)에서의 가짜 수렴을 방回避한다.

주요 결과

단계 1: 알고리즘 선택 ($n \le 10^4$)

단일 NVIDIA GB200 GPU에서 11개의 방법이 안정적으로 수렴했다. 그러나 엄격한 효율성 임계값( $n=10^4$에서 4초 이내 수렴)을 충족한 것은 6개뿐이었다:

• ADMM
• RMSprop
• Block-SVRG AdaptGrow
• AdaGrad
• Row-Stochastic SVRG
• Piecewise AdaGrad

다중 업데이트, 표준 PGD, 딥 언폴딩은 수렴에 실패하거나 현저히 느렸다. 2차 방법론(L-BFGS, Newton)은 곡률 근사 문제나 메모리 문제로 인해 TPDM 스펙트럼에서 실패했다.

단계 2: 대규모 실행 가능성 ($n = 10^5, 10^6$)

선택된 6개의 방법은 멀티 노드 GPU 클러스터(최대 64개 GPU)에서 테스트되었다.

• AdaGrad 제품군의 우세: 5개의 AdaGrad 제품군(AdaGrad, Piecewise, Row-Stoch SVRG, Block-SVRG AdaptGrow, RMSprop)이 $n=10^6$에서 성공적으로 수렴했다. ADMM은 이 규모에서 속도 문제로 제외되었다.
• 스펙트럼 의존성: "가장 빠른" 솔버는 행렬의 스펙트럼에 따라 달라진다:
  • 상관 계수 행렬 (지배적인 저계수 스펙트럼): 풀 배치(Full-batch) AdaGrad가 가장 빠르다. 이 문제는 깨끗한 신호-노이즈 갭을 가지고 있어, 풀 배치 단계가 효율적인 짧은 실행만으로 충분하다.
  • TPDM (평탄하고 조건수가 나쁜 스펙트럼): Block-SVRG AdaptGrow가 가장 빠르다. 스펙트럼이 근사 0의 갭을 가진 공통 요인에 의해 지배되므로 긴 실행이 필요하다. 적응형 블록 샘플링 전략의 낮은 반복당 비용이 더 많은 반복 횟수의 필요성을 상쇄한다.
• 성능: $n=10^6$에서 Block-SVRG AdaptGrow는 TPDM을 약 4분(409회 반복) 만에 해결한 반면, AdaGrad는 상관 계수를 약 2분(72회 반복) 만에 해결했다.

클러스터링 베이스라인

본 논문은 구형 K-means(Spherical K-means)(S의 행에 적용됨)를 하드 라벨 대안으로 벤치마킹한다.

• 효율성: 각도 기반 클러스터 구조가 존재할 경우 K-means는 훨씬 더 빠르다(더 적은 반복 횟수).
• 퇴화(Degeneracy): 행렬이 단일 공통 요인으로 붕괴하는 경우(유효 계수가 매우 낮아 $r_{\text{eff}} \to 1$인 상황, 대규모 TPDM에서 흔함), K-means는 실패한다(실루엣 계수 $\approx 0$). 이러한 경우 SymNMF가 제공하는 소프트 팩터화가 여전히 필요하다.

의의 및 주장

본 논문은 이론적 SymNMF와 대규모 실무적 금융 리스크 추정 사이의 간극을 메운다고 주장한다. 주요 기여는 다음과 같다:

1. 확장성: 트레이스 항등식 재정식화와 멀티 GPU 분산을 통해 밀집(dense) SymNMF가 $n=10^6$까지 실행 가능하다는 것을 입증함으로써, $O(n^2)$ 메모리 병목 현상을 제거했다.
2. 솔버 권장 사항: 입력 유형과 규모에 따른 솔버 선택을 위한 데이터 기반 가이드를 제공한다. 짧은 실행에는 Diagonal AdaGrad를, 길고 조건수가 나쁜 실행에는 Block-SVRG AdaptGrow를 기본으로 권장한다.
3. 알고리즘 혁신: AdaGrad의 무한 메모리(정상적 목적 함수에 유리)와 긴 실행 시 발생하는 포화(saturation) 사이의 긴장을 해결하는 특정 엔지니어링 확장(Piecewise AdaGrad, Block-SVRG AdaptGrow)을 도입하고 검증했다.
4. 제약 조건 처리: 투영과 Softplus 간의 규모별 트레이드오프를 규명하고, 대규모 환경의 장기 메모리 적응형 방법론에 대해 Softplus 사용을 지양하도록 조언한다.

저자들은 이러한 발견이 SymNMF 최적화 지형 자체의 특성이며, 사용된 특정 금융 입력뿐만 아니라 유사한 스펙트럼 특성을 가진 모든 문제에 적용 가능함을 강조한다.