A Block Coordinate Descent Method for Nonsmooth Composite Optimization under Orthogonality Constraints

기술 요약: 직교성 제약 하의 비연속 합성 최적화를 위한 블록 좌표 강하법

문제 정의
본 논문은 직교성 제약 하의 비연속 합성 최적화 문제를 다루며, 다음과 같이 수식화됩니다:
$$\min_{X \in \mathbb{R}^{n \times r}} F(X) \triangleq f(X) + h(X), \quad \text{s.t. } X^T X = I_r$$
여기서 $n \ge r$이며, $f(X)$는 매끄러운 (비볼록일 수 있는) 함수이고, $h(X)$는 좌표별 분리 가능한 적절한 하반연속 비연속 함수입니다. 실현 가능 집합은 스티펠 다양체 $\mathcal{M} = \text{St}(n, r)$입니다. 이 프레임워크는 $\ell_0$ 또는 $\ell_1$ 정규화를 포함한 희소 주성분 분석 (PCA), 비음수 PCA, 직교성 제약이 있는 심층 신경망 학습, 그리고 사전 학습과 같은 통계적 학습 및 데이터 과학의 중요한 응용 분야를 포괄합니다.

기존 방법들은 다음과 같은 중대한 한계를 겪고 있습니다: 많은 방법들이 전체 기울기 정보에 의존하여 (높은 계산 비용), 좌표별 비연속 목적 함수를 효과적으로 처리하지 못하며, 진정한 감소 속성을 결여하고 있거나 (대개 점근적 실현 가능성만 달성), 약한 최적성 보장을 제공합니다 (표준 임계점에만 수렴).

방법론: OBCD 알고리즘
저자들은 $k \ge 2$인 해 행렬 $X$의 $k$개의 행을 동시에 업데이트하는 실현 가능한 방법인 OBCD(Orthogonal Block Coordinate Descent) 를 제안합니다.

1. 제약 조건 보존 업데이트 체계:
   다양체 위로의 투영이나 재구축 (retractions) 을 사용하는 대신, OBCD 는 구성상 직교성을 유지하는 특정 업데이트 규칙을 사용합니다. 행 인덱스의 작업 집합 $B$(크기 $k$) 에 대해 업데이트는 다음과 같이 정의됩니다:
   $$X^{t+1} = X^t + U_B (V - I_k) U_B^T X^t$$
   여기서 $U_B$는 $B$에 있는 행들을 선택하며, $V \in \text{St}(k, k)$는 부분 문제를 해결하는 직교 행렬입니다. 보조정리 2.1 은 $X^t$가 실현 가능하면 임의의 $V \in \text{St}(k, k)$에 대해 $X^{t+1}$도 실현 가능함을 증명합니다.

2. 부분 문제 공식화:
   각 반복에서 OBCD 는 $k \times k$ 차원의 스티펠 다양체 상의 소규모 부분 문제를 풉니다. Majorization-Minimization (MM) 접근법을 사용하여 매끄러운 부분 $f(X)$는 2 차 대리 함수로 근사되고, 비연속 부분 $h(X)$는 정확하게 유지됩니다. 결과적으로 도출된 부분 문제는 다음과 같습니다:
   $$\bar{V}_t \in \arg\min_{V \in \text{St}(k, k)} \left( \frac{1}{2} \|V - I_k\|_{\tilde{Q}}^2 + \langle V, P \rangle + h(V Z) \right)$$
   여기서 $Z = U_B^T X^t$, $P$는 $f$의 기울기를 포함하며, $\tilde{Q}$는 $f$의 헤시안 또는 스칼라 대리 변수에서 유도된 양정치 행렬입니다.

3. 부분 문제 해결:

   • 일반적인 $k$: 논문은 부분 문제를 정확히 또는 효율적으로 (예: proximal-친화적 구조를 통해) 풀 수 있다고 가정합니다.
   • 경우 $k=2$: 저자들은 새로운 **Breakpoint Search Method (BSM)**를 소개합니다. Givens 회전 ($V^{rot}_\theta$) 과 Jacobi 반사 ($V^{ref}_\theta$) 를 사용하여 $2 \times 2$ 직교 행렬을 매개변수화함으로써, 부분 문제를 $\theta$에 대한 1 차원 최적화로 축소합니다. BSM 은 목적 함수의 모든 브레이크포인트 (비연속 항 $h$에서 비롯된 임계점 포함) 를 식별하여 전역 최소값을 찾습니다.

4. 작업 집합 선택:
   이 알고리즘은 작업 집합 $B$를 선택하기 위한 무작위 및 순환 전략 모두를 지원합니다.

이론적 기여
본 논문은 최적성과 수렴에 관한 엄밀한 이론적 분석을 제공합니다:

• 업데이트 체계의 완전성: 저자들은 제안된 행별 업데이트 체계가 완전함을 증명합니다. 구체적으로, 스티펠 다양체 위의 임의의 점은 이러한 $k$-행 업데이트의 시퀀스를 통해 다른 임의의 실현 가능한 점으로부터 도달할 수 있습니다 (정리 3.1, 코롤러리 3.2).
• 강화된 최적성 조건: 논문은 **Global Block-$k$ Stationary Points (BSk-points)**를 정의합니다. 해가 BSk-점이 되려면 $k$개의 행으로 구성된 임의의 블록을 최적화하여 개선할 수 없어야 합니다. 저자들은 다음과 같은 최적성의 위계 관계를 수립합니다:
  $$\{\text{Global Optima}\} \subseteq \{\text{BSk-points}\} \subseteq \{\text{BS(k+1)-points}\} \subseteq \{\text{Critical Points}\}$$
  이는 BSk-점 ($k \ge 2$) 이 표준 임계점보다 엄격하게 더 강한 최적성 조건을 만족함을 의미하며, 이론적으로 기존 방법들이 갇히는 나쁜 국소 최소값에서 탈출할 수 있게 합니다.
• 반복 복잡도:
  • OBCD 는 $O(1/\epsilon)$의 반복 복잡도로 $\epsilon$-block-$k$ 정상점을 찾습니다.
  • Kurdyka–Łojasiewicz (KL) 부등식 가정 하에서, 논문은 비에르고딕 (마지막 반복) 수렴 속도를 수립합니다. KL 지수 $\sigma$에 따라 수렴은 유한 ($\sigma=0$), 선형 ($\sigma \in (0, 1/2]$), 또는 아선형 ($\sigma \in (1/2, 1)$) 입니다.

실험 결과
저자들은 MNIST, Gisette, 20News 와 같은 실제 데이터셋과 합성 데이터를 사용하여 L0 정규화 희소 PCA, L1 정규화 희소 PCA, 그리고 비음수 PCA 에 대해 OBCD 를 평가했습니다.

• 성능: OBCD 는 Linearized ADMM (LADMM), Riemannian ADMM (RADMM), Penalty-based Splitting Method (PSM), Manifold Proximal Gradient (ManPG) 를 포함한 최첨단 베이스라인보다 일관되게 우수한 성능을 발휘합니다.
• 목적 함수 값: 최종 목적 함수 값 측면에서 OBCD 는 경쟁 방법들보다 낮은 값을 달성하며, 종종 다른 방법들이 갇히는 국소 최소값을 탈출합니다.
• 효율성: 전체 기울기 방법들이 더 적은 반복을 필요로 할 수 있지만, OBCD 의 낮은 반복당 비용 (부분 기울기 업데이트) 은 CPU 시간으로 측정할 때 우수한 성능을 가져옵니다.
• 실현 가능성: 일부 제약 조건을 극한에서만 만족하는 실현 불가능한 방법들 (예: 특정 분할 방법) 과 달리, OBCD 는 최적화 과정 전반에 걸쳐 엄격한 직교성 (비음수 PCA 변형의 경우 비음수성 포함) 을 유지합니다.

의의 및 주장
본 논문은 OBCD 가 계산 효율성과 강력한 이론적 보장을 결합함으로써 중요한 발전을 이루었다고 주장합니다. 그 주요 의의는 다음과 같습니다:

1. 비연속성 처리: 직교성 제약 하의 좌표별 비연속 목적 함수를 효과적으로 해결하며, 이는 많은 기존 다양체 최적화 방법들이 어려움을 겪는 영역입니다.
2. 강화된 최적성: 블록 업데이트 ($k \ge 2$) 를 활용함으로써 BSk-점을 목표로 하는데, 이는 이론적으로 표준 임계점보다 우수하여 비최적 국소 최소값을 피할 수 있는 메커니즘을 제공합니다.
3. 실현 가능성: 이는 엄밀한 실현 가능 방법으로, 모든 반복에서 제약 조건이 만족되도록 보장하며, 페널티 기반 또는 실현 불가능한 분할 접근법과 다릅니다.
4. 실용적 효율성: 이 알고리즘은 전체 기울기 계산이 불가능한 대규모 문제를 위해 설계되었으며, 검증된 수렴 속성을 가진 확장 가능한 대안을 제공합니다.