Convergence and complexity of block majorization-minimization for constrained block-Riemannian optimization

이 논문은 리만 다양체 상의 제약 조건을 가진 블록 좌표 최적화 문제를 해결하기 위한 블록 대변화 - 최소화 (BMM) 알고리즘의 점근적 수렴성과 $\widetilde{O}(\epsilon^{-2})$ 반복 횟수 내의 $\epsilon$-정상점 도달 복잡도를 증명하고, 다양한 리만 제약 알고리즘에 적용 가능함을 이론적으로 분석하며 실험적으로 검증했습니다.

핵심

1. 배경: 우리가 어디에 서 있는가? (리만 다양체란?)

일반적인 수학 문제 (유클리드 공간) 는 평평한 평지에서 문제를 푸는 것과 같습니다. 하지만 이 논문이 다루는 문제는 구 (공), 원기둥, 혹은 구불구불한 산길 같은 곳에서 문제를 푸는 것입니다.

• 비유: 우리가 평지에서 길을 찾을 때는 직선으로 가면 되지만, 지구 (구면) 위에서 길을 찾을 때는 직선으로 갈 수 없습니다. 지구는 둥글기 때문에 '대원 (Great Circle)'을 따라 가야 합니다.
• 문제: 이런 구불구불한 지형 (리만 다양체) 에서, 그리고 **여러 개의 변수 (블록)**가 서로 얽혀 있을 때, 가장 낮은 곳 (최소값) 을 찾는 것은 매우 어렵습니다.

2. 해결책: "가상의 언덕"을 만드는 방법 (대우 - 최소화, MM)

이 논문이 제안하는 RBMM (리만 블록 대우 - 최소화) 알고리즘은 다음과 같은 전략을 씁니다.

• 상황: 우리가 산 정상에서 내려가고 싶지만, 지형이 너무 복잡해서 어디로 가야 할지 모릅니다.
• 전략 (대우 - 최소화):
  1. 가상의 지도 만들기: 현재 서 있는 위치를 기준으로, 실제 지형보다 더 높거나 같은 (안전한) 가상의 언덕을 그립니다. 이 가상의 언덕은 실제 지형보다 훨씬 단순하고 평평합니다.
  2. 가상 언덕 내려가기: 복잡한 실제 지형 대신, 이 단순한 가상의 언덕을 따라 내려갑니다.
  3. 위치 업데이트: 가상의 언덕에서 가장 낮은 곳에 도착하면, 그 위치를 실제 지형의 새로운 위치로 삼습니다.
  4. 반복: 새로운 위치에서 다시 가상의 지도를 그리고, 또 내려갑니다.

이 과정을 반복하면, 우리는 결국 실제 지형의 가장 낮은 곳 (최적해) 에 도달하게 됩니다.

3. 핵심 아이디어: "조각조각" 나누기 (블록 최적화)

문제가 너무 크다면 한 번에 해결하기 어렵습니다. 그래서 블록 (Block) 단위로 쪼개서 풉니다.

• 비유: 거대한 퍼즐을 한 번에 맞추려 하지 말고, 한 조각씩 맞춰 나가는 것입니다.
• 작동 방식:
  • 1 번 조각 (블록) 을 고정하고, 2 번 조각만 움직여 최적의 위치를 찾습니다.
  • 그다음 2 번 조각을 고정하고, 3 번 조각을 움직입니다.
  • 이 과정을 모든 조각에 대해 순서대로 반복합니다.
• 장점: 이렇게 하면 한 번에 모든 변수를 계산할 필요 없이, 하나씩 천천히 최적화할 수 있어 계산이 훨씬 빨라집니다.

4. 이 연구의 주요 성과 (왜 중요한가?)

이 논문은 이 방법이 "언제, 얼마나 빨리, 얼마나 정확하게" 작동하는지를 수학적으로 증명했습니다.

1. 안정성 (수렴성):

   • 비록 우리가 엉뚱한 곳에서 시작하더라도 (임의의 초기값), 이 알고리즘을 계속 돌리면 반드시 산의 골짜기 (국소 최적점) 에 도달한다는 것을 증명했습니다.
   • 비유: 아무리 길을 잘못 들어섰더라도, 이 지도를 따라가면 결국 골짜기에는 꼭 도착합니다.

2. 속도 (복잡도):

   • "오차 (ε)"를 얼마나 줄이려면 몇 번의 반복이 필요한지 계산했습니다.
   • 결과: 오차를 줄이기 위해 필요한 반복 횟수가 약 $1/\epsilon^2$ 정도라는 것을 증명했습니다. 이는 기존에 알려진 방법들보다 훨씬 효율적이며, 특히 Stiefel 다양체 (직교 행렬이 필요한 문제) 같은 실제 응용 분야에서 매우 강력한 성능을 보입니다.

3. 실용성 (근사 해법 허용):

   • 완벽한 정답을 구하는 것은 시간이 너무 오래 걸릴 수 있습니다. 이 알고리즘은 완벽하지는 않지만 "충분히 좋은" 근사 해를 구해도 작동하도록 설계되었습니다.
   • 비유: 완벽한 정답을 찾기 위해 100% 정확히 계산할 필요 없이, 99% 정확해도 충분하다면 그걸로 진행해도 된다는 뜻입니다.

5. 어디에 쓰일까요? (실제 응용 사례)

이 이론은 단순히 수학 책에 그치는 것이 아니라, 다음과 같은 실제 문제들을 해결하는 데 쓰입니다.

• 강건한 PCA (Robust PCA): 사진이나 데이터에서 **노이즈 (오염)**를 제거하고 핵심 정보만 남길 때 (예: 흐릿한 사진에서 얼굴만 선명하게).
• 서브스페이스 추적 (Subspace Tracking): 시간에 따라 변하는 데이터 (예: 움직이는 물체의 궤적) 를 실시간으로 추적할 때.
• 딕셔너리 학습 (Dictionary Learning): 복잡한 데이터를 더 간단한 기본 요소들의 조합으로 표현할 때 (예: 이미지 압축).

6. 요약: 한 줄로 정리하면?

"이 논문은 복잡하고 구불구불한 지형 (리만 다양체) 에서, 퍼즐 조각을 하나씩 맞추며 (블록 최적화), 가상의 지도를 그려가며 (대우 - 최소화) 문제를 해결하는 알고리즘이 매우 안정적이고 빠르다는 것을 수학적으로 증명했습니다."

이 연구 덕분에, 인공지능과 데이터 과학 분야에서 매우 복잡한 제약 조건을 가진 문제들을 더 빠르고 정확하게 풀 수 있는 길이 열렸습니다.

기술 요약

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

• 배경: 리만 다양체 (Riemannian manifold) 상의 최적화는 선형 대수 분해, 비선형 제약 조건이 있는 문제, 형태 공간 분석, 자동 학습 등 다양한 분야에서 필수적입니다. 기존 방법들은 주로 지수 사상 (exponential map) 을 따라 하강 방향을 계산하는 방식에 의존하지만, 이는 계산적으로 비용이 크거나 근사화가 필요한 경우가 많습니다.
• 문제 정의: 본 논문은 다음과 같은 제약된 블록 리만 최적화 문제를 다룹니다.
  $$\min_{\theta} f(\theta) \quad \text{s.t.} \quad \theta^{(i)} \in \Theta^{(i)} \subseteq \mathcal{M}^{(i)}, \quad i=1,\dots,m$$
  여기서 $f$는 매끄럽지만 비볼록 (nonconvex) 인 목적 함수이며, 각 블록 $\theta^{(i)}$는 리만 다양체 $\mathcal{M}^{(i)}$의 닫힌 부분 집합 $\Theta^{(i)}$에 속합니다.
• 도전 과제:
  1. 비볼록 문제이므로 전역 최적해 대신 **정상점 (stationary point)**으로의 수렴을 보장해야 합니다.
  2. 블록 좌표 하강 (Block Coordinate Descent, BCD) 방식은 블록 수가 3 이상일 때 정상점으로 수렴하지 않을 수 있는 반례 (Powell, 1973) 가 존재합니다.
  3. 리만 다양체 위에서의 반복 횟수 복잡도 (iteration complexity), 즉 $\epsilon$-정상점을 찾기 위한 최악의 경우 반복 횟수를 규명하는 것이 이론적, 실용적으로 중요합니다.
  4. 서브문제 (surrogate minimization) 의 해를 정확히 구하지 못할 때 (inexact computation) 도 알고리즘이 견고하게 동작해야 합니다.

2. 제안 방법론 (Methodology)

저자들은 리만 블록 대역화 - 최소화 (Riemannian Block Majorization-Minimization, RBMM) 알고리즘을 제안하고 분석합니다.

• 알고리즘 구조 (RBMM):
  1. 각 블록 $i$에 대해, 현재 점 $\theta^{(i)}_{n-1}$에서 목적 함수 $f^{(i)}_n$을 상한 (upper bound) 하는 대역화 함수 (majorizing surrogate) $g^{(i)}_n$을 구성합니다.
  2. $g^{(i)}_n$을 $\Theta^{(i)}$ 위에서 최소화하여 다음 반복점 $\theta^{(i)}_n$을 업데이트합니다.
  3. 다른 블록들은 고정된 채로 순환적으로 (cyclic order) 이 과정을 반복합니다.
• 대역화 함수 (Surrogates) 의 종류:
  1. g-smooth surrogate: 리만 다양체 위에서의 기하학적 매끄러움 (geodesic smoothness) 을 만족하는 함수.
  2. Riemannian Proximal surrogate: $g^{(i)}_n(\theta) = f^{(i)}_n(\theta) + \frac{\lambda_n}{2} d^2(\theta, \theta^{(i)}_{n-1})$. (리만 거리 제곱 사용)
  3. Euclidean Proximal surrogate: $g^{(i)}_n(\theta) = f^{(i)}_n(\theta) + \frac{\lambda_n}{2} \|\theta - \theta^{(i)}_{n-1}\|^2$. (유클리드 거리 제곱 사용, 임베딩된 다양체에서 계산 효율성 확보)
• 핵심 가정:
  • 목적 함수와 대역화 함수의 매끄러움 (g-smoothness 또는 Euclidean L-smoothness).
  • 제약 집합의 기하학적 성질 (Hadamard 다양체, Stiefel 다양체 등).
  • 비정확 계산 (Inexact computation): 최적화 서브문제의 해가 정확하지 않더라도 오차 (optimality gap) 가 충분히 빠르게 감소하여 합산 가능 (summable) 해야 함.

3. 주요 기여 및 결과 (Key Contributions & Results)

3.1. 점근적 수렴성 (Asymptotic Convergence)

• 1 또는 2 블록 ($m \le 2$): 제약 집합이 강하게 geodesically convex 할 때, RBMM 알고리즘의 모든 극한점은 목적 함수의 정상점으로 수렴함을 증명 (Theorem 3.2).
• 다중 블록 ($m \ge 3$): Powell 의 반례를 극복하기 위해, 대역화 함수가 거리 정규화 항 (distance-regularizing term, 예: proximal term) 을 포함하도록 가정함. 이 경우 제약 집합의 볼록성 없이도 모든 극한점이 정상점으로 수렴함을 증명 (Theorem 3.3). 이는 기존 BCD 방법들의 한계를 보완합니다.

3.2. 반복 횟수 복잡도 (Iteration Complexity)

비볼록 최적화에서 $\epsilon$-정상점을 찾기 위한 반복 횟수 상한을 제시했습니다.

• Riemannian/Euclidean Proximal Surrogates: 제약 집합이 geodesically convex 일 때, 복잡도가 $\tilde{O}(\epsilon^{-2})$임을 증명 (Theorem 3.5).
  • 이는 기존 리만 최적화 알고리즘 중 블록 단위에서 이 복잡도 결과를 제공한 최초의 연구 중 하나입니다.
• g-smooth Surrogates: 일반적인 매끄러운 대역화 함수를 사용할 때, 추가 조건 하에 $\tilde{O}(\epsilon^{-2})$ 복잡도를 달성함을 보임 (Theorem 3.6).
• Stiefel 다양체 적용: Stiefel 다양체 (직교 프레임의 집합) 와 유클리드 공간의 곱집합에서, 목적 함수와 대역화 함수가 유클리드 의미에서 $L$-smooth 하면, 위 복잡도 결과가 성립함을 보임 (Corollary 3.7). 이는 실제 계산에서 유클리드 거리 기반의 근사 (Euclidean proximal surrogate) 를 사용할 수 있게 하여 계산 효율성을 높입니다.

3.3. 견고성 (Robustness)

알고리즘이 서브문제의 해를 정확히 구하지 못하더라도 (inexact solution), 오차가 합산 가능 (summable) 하기만 하면 수렴성과 복잡도 결과가 유지됨을 보였습니다. 이는 실제 응용에서 수치적 오차나 근사 해를 사용하는 경우를 포괄합니다.

4. 응용 사례 (Applications)

본 이론은 다음과 같은 다양한 알고리즘과 문제에 적용되어 새로운 수렴성 및 복잡도 결과를 도출했습니다:

1. 지오데식 제약 서브스페이스 추적 (Geodesically constrained subspace tracking): Stiefel 다양체 위의 블록 MM 알고리즘에 적용하여 $\tilde{O}(\epsilon^{-2})$ 복잡도 증명.
2. Fisher-Rao 거리 하의 낙관적 가능도 (Optimistic likelihood): 양의 정부호 행렬 다양체 (Hadamard manifold) 위의 블록 Riemannian proximal 업데이트 적용.
3. 리만 CP-사전 학습 (Riemannian CP-dictionary learning): 텐서 분해 문제에서 Stiefel 또는 저차원 (low-rank) 다양체 제약 하의 블록 최적화.
4. 강건한 PCA (Robust PCA): 저차원 행렬 다양체 (low-rank manifold) 상의 최적화 문제.

5. 의의 및 중요성 (Significance)

1. 이론적 공백 해소: 기존 리만 최적화 연구는 주로 단일 블록 (one-block) 이나 점근적 수렴성에 집중했으나, 본 논문은 블록 단위 (multi-block) 최적화에 대한 **반복 횟수 복잡도 (iteration complexity)**를 체계적으로 정립했습니다.
2. 계산 효율성과 이론의 결합: 복잡한 리만 거리 (geodesic distance) 를 사용하는 대신, 유클리드 거리 기반의 근사 (Euclidean proximal surrogate) 를 사용하더라도 Stiefel 다양체 등 특정 구조에서는 동일한 복잡도 보장이 가능함을 보였습니다. 이는 실제 구현 시 계산 비용을 크게 줄일 수 있음을 의미합니다.
3. 일반성: Hadamard 다양체, Stiefel 다양체, 고정 랭크 행렬 다양체 등 다양한 기하학적 구조를 포괄하는 일반적인 프레임워크를 제공하며, 기존에 복잡도 분석이 없었던 여러 알고리즘 (예: Breloy et al. [BKSP21] 의 MM 방법 등) 에 대해 최초의 복잡도 상한을 제시했습니다.
4. 실제 검증: 합성 데이터 실험을 통해 제안된 RBMM 알고리즘이 기존 유클리드 기반 알고리즘을 리만 설정에 적용한 것보다 더 빠르게 수렴함을 확인했습니다.

결론적으로, 본 논문은 제약된 리만 다양체 상의 비볼록 블록 최적화 문제에 대해 강력한 수렴성 보장과 최적의 반복 횟수 복잡도 ($\tilde{O}(\epsilon^{-2})$) 를 제공하는 포괄적인 이론적 기반을 마련했습니다.