Nonconvex Matrix Factorization is Geodesically Convex: Global Landscape Analysis for Fixed-rank Matrix Optimization From a Riemannian Perspective

기술 요약: 비볼록 행렬 분해는 측지적 볼록성을 가진다 (Nonconvex Matrix Factorization is Geodesically Convex)

문제 정식화
본 논문은 일반적인 고정 랭크 양의 준정부호(PSD) 행렬 최적화 문제를 조사한다:
$$\min_{0 \preceq X \in \mathbb{S}^p, \text{rank}(X)=r} f(X)$$
여기서 $0 < r \leq p$이다. 랭크 제약 조건을 처리하기 위해, 저자들은 Burer-Monteiro 분해를 사용하여, $X = YY^\top$를 만족하는 풀 랭크(full column rank) 직사각형 행렬 $Y \in \mathbb{R}^{p \times r}$에 대한 문제로 재작성한다. 결과적으로 나타나는 비볼록 목적 함수는 $\bar{h}(Y) = f(YY^\top)$이다.

저자들은 이 분해의 전역적 지형(global landscape) 분석과 관련하여 기존 문헌의 세 가지 구체적인 한계점을 다룬다:

1. 기하학적 해석: 유클리드 기반의 기존 분석들은 종종 비직관적인 정칙성 조건(regularity conditions)이나 제한된 방향에 의존한다. 저자들은 고전적인 볼록성 개념을 사용하여 더 명확한 설명을 제공하고자 한다.
2. 노이즈 처리: 대부분의 기존 전역 지형 결과는 노이즈가 없는 설정($\nabla f(X^*) = 0$)을 가정한다. 본 논문은 이 그래디언트가 0이 아닐 수 있는 일반적인 노이즈가 존재하는 환경에서도 지형을 분석하는 것을 목표로 한다.
3. 가정의 강도: 이전 연구들은 $f$가 전역적으로 또는 임계점 근처에서 제한적 강볼록성(RSC) 및 매끄러움(RSM)을 충족할 것을 요구하는 경우가 많다. 저자들은 국소적 결과를 위해 이를 제한적 엄격 볼록성(restricted strict convexity)으로 완화하고자 한다.

방법론: 리만 몫 기하학 (Riemannian Quotient Geometry)
핵심적인 방법론적 혁신은 몫 다양체(quotient manifold) 상의 리만 최적화를 적용하는 것이다. 저자들은 $X = YY^\top$ 분해가 직교 변환($Y \to YO$, 여기서 $O \in \mathcal{O}_r$)에 의한 불변성을 도입한다는 점을 인식한다.

• 탐색 공간: 저자들은 탐색 공간을 몫 다양체 $\mathcal{M}^q_{r+} := \widetilde{\mathcal{M}}^q_{r+} / \mathcal{O}_r$로 정의하며, 여기서 $\widetilde{\mathcal{M}}^q_{r+}$는 풀 랭크 $p \times r$ 행렬들의 집합이다.
• 메트릭: 전체 공간에는 유클리드 메트릭 $\bar{g}_Y(\eta_Y, \theta_Y) = \text{tr}(\eta_Y^\top \theta_Y)$가 부여된다. 이는 몫 다양체 상에 리만 메트릭을 유도한다.
• 핵심 통찰: $\bar{h}(Y)$라는 유클리드 목적 함수는 회전 대칭성 때문에 본질적으로 비볼록하지만(따라서 임의의 정체점 근처에서 볼록할 수 없음), 몫 다양체 상의 유도된 목적 함수 $h([Y])$는 **측지적 볼록성(geodesic convexity)**을 보일 수 있다.
• 동등성: 결정적으로, 몫 다양체 상의 리만 그래디언트와 헤시안은 수평 공간(horizontal space)으로 제한되었을 때 $\bar{h}(Y)$의 유클리드 그래디언트 및 헤시안과 정확히 일치한다. 이는 표준 그래디언트 하강 알고리즘(유클리드 공간에서 작동하는)이 이 몫 다양체 상의 리만 그래디언트 하강과 계산적으로 동일함을 의미하며, 이를 통해 저자들이 기하학적 보증을 표준 알고리즘으로 전달할 수 있게 한다.

주요 기여 및 결과

1. 다양체의 기하학적 특성
저자들은 몫 다양체 $\mathcal{M}^q_{r+}$의 근본적인 기하학적 특성을 확립한다:

• 측지적 볼록 반경: $[Y]$를 중심으로 하고 반지름이 $x \leq \sigma_r(Y)/3$인 측지 볼(geodesic ball)이 측지적으로 볼록함을 증명한다. 이 반지름은 상수 계수 내에서 샤프(sharp)하다.
• 의의: 이 결과는 Bures-Wasserstein 기하학 하에서 Bures-Wasserstein 공간($r=p$인 경우)에 대한 최초의 명시적인 측지 볼록 반경을 제공한다.

2. 전역 지형 분석 (RSC 및 RSM 하에서)
$f$가 $(2r, 4r)$-제한적 강볼록성 및 매끄러움 성질을 만족할 때, 저자들은 목적 함수의 전역 지형을 세 가지 뚜렷한 영역으로 특징짓는다 (정리 1, 따름정리 1):

• 영역 R1 (타겟 근처): 실제 파라미터 $X^*$의 근방에서 목적 함수 $h([Y])$는 측지적 강볼록성 및 매끄러움을 가진다. 이 영역은 실제 해와의 거리가 조건수(condition number) 및 최소 특이값에 비해 작을 때로 정의된다.
• 영역 R2 (엄격한 안장점): 엄격한 안장점(strict saddle points)의 근방에서 리만 헤시안은 적어도 하나의 음의 고윳값을 가지며, 탈출 가능한 방향이 명시적으로 제공된다.
• 영역 R3 (타겟에서 먼 곳): 나머지 영역에서는 리만 그래디언트의 크기가 크다.

이러한 "양호한 지형(benign landscape)" 구조(해 근처의 강볼록성, 안장점에서의 음의 곡률, 그 외 영역에서의 큰 그래디언트)는 **강건한 엄격 안장점 성질(robust strict saddle property)**을 만족하는 알고리즘(예: 섭동된 리만 그래디언트 하강법)이 전역 최솟값으로 수렴함을 보장한다.

3. 국소 지형 분석 (제한적 엄격 볼록성 하에서)
$f$가 오직 $(r, 2r)$-제한적 엄격 볼록성을 만족하는 더 약한 가정 하에서, 저자들은 임의의 국소 최솟값 주변에 목적 함수가 측지적으로 볼록해지는 근방이 존재함을 보여준다. 이는 기하학적 분석의 적용 범위를 강볼록성 영역 너머로 확장한다.

4. 노이즈 설정 분석
$\nabla f(X^*) = 0$을 가정하는 기존 연구들과 달리, 본 분석은 $\nabla f(X^*) \neq 0$인 노이즈가 있는 경우를 명시적으로 다룬다. 지형 특성(예: 강볼록성 반경 및 그래디언트의 크기)에 대한 경계값은 실제 파라미터에서의 그래디언트 노름 $\|\nabla f(X^*)\|$에 의존한다. 결과에 따르면 노이즈 수준이 제어되는 한 양호한 지형 구조는 유지된다.

5. 반복 복잡도
이러한 지형 결과를 행렬 근사 문제(일반적인 설정의 특정 사례)에 적용하여, 저자들은 국소 개선 기능이 있는 섭동된 리만 그래디언트 하강 알고리즘의 반복 복잡도 경계를 도출한다. 무작위 초기화를 사용할 경우, 초기화가 특정 스펙트럼 조건을 만족한다면(이는 높은 확률로 성립함이 입증됨) 알고리즘은 $O(\log(1/\epsilon) + \log^4(p))$ 번의 반복 만에 $\epsilon$-정확도에 도달함을 보여준다.

의의 및 주장
본 논문은 몫 리만 기하학 하에서 Burer-Monteiro 분해된 목적 함수의 최초의 전역 지형 분석을 제공한다고 주장한다. 주요 의의는 다음과 같다:

• 기하학적 설명: 단순한 국소 정칙성 조건이 아니라, 몫 다양체 상의 측지적 강볼록성에 기인하여 Burer-Monteiro 분해에서 바닐라 그래디언트 하강법이 성공하는 이유에 대한 완전한 기하학적 설명을 제공한다.
• 일반성: 결과는 노이즈가 있는 경우와 없는 경우를 모두 다루며, 최소제곱법뿐만 아니라 RSC/RSM을 만족하는 일반적인 목적 함수에 적용된다.
• 샤프함(Sharpness): 도출된 볼록성 반경($\sigma_r(Y)/3$)은 상수 범위 내에서 샤프하다.
• 알고리즘적 함의: 이 분석은 그래디언트 기반 방법들이 왜 실제 환경에서 가짜 국소 최솟값이나 안장점을 피하고 전역 수렴을 하는지에 대한 이론적 토대를 제공한다.

저자들은 제한적 강볼록성 파라미터 $\delta$에 대한 조건이 최근의 국소 분석만큼 정교하지 않을 수 있지만, 그들의 결과가 갖는 기하학적 성격(단순한 정칙성이 아닌 볼록성을 제공함)이 알고리즘 성능에 대해 더 직관적이고 강력한 설명을 제공한다고 언급한다. 또한 과잉 매개변수화(over-parameterized) 설정에서의 지형 탐구 및 측지적 볼록성 반경을 최대화하는 메트릭 식별과 같은 향후 연구 방향을 제시한다.