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

技術要約：非凸行列分解は測地線凸である

問題の定式化
本論文は、一般的な固定ランクの正定値（PSD）行列最適化問題に関する研究である：
$$\min_{0 \preceq X \in \mathbb{S}^p, \text{rank}(X)=r} f(X)$$
ここで $0 < r \leq p$ である。ランク制約を扱うために、著者らはブラー・モンテイロ（Burer-Monteiro）分解を用い、フル列ランクを持つ長方形行列 $Y \in \mathbb{R}^{p \times r}$ を用いて、 $X = YY^\top$ と書き換える。その結果得られる非凸目的関数は $\bar{h}(Y) = f(YY^\top)$ である。

著者らは、この分解に関する既存の文献における3つの具体的な制限事項に対処している：

1. 幾何学的解釈： 従来のユークリッド空間に基づく解析は、直感的でない正則性条件や制限された方向に依存することが多い。著者らは、古典的な幾何学的概念である凸性を用いて、より明快な説明を試みている。
2. ノイズの扱い： 既存のほとんどのグローバルな景観（ランドスケープ）に関する結果は、真のパラメータ $X^*$ において $\nabla f(X^*) = 0$ となる無ノイズの設定を仮定している。本論文は、この勾配がゼロにならない一般的なノイズを含む設定における景観の解析を目指している。
3. 仮定の強さ： 従来の研究では、$f$ がグローバルに、あるいは停留点の近傍で制限強凸性（RSC）および滑らかさ（RSM）を満たすことを要求することが多い。著者らは、局所的な結果のために、これらの仮定を「制限厳密凸性」へと緩和することを目指している。

手法：リーマン商幾何学
本研究の核心的な手法上の革新は、商多様体上のリーマン最適化の適用である。著者らは、分解 $X = YY^\top$ が直交変換（任意の $O \in \mathcal{O}_r$ に対する $Y \to YO$）の下での不変性を導入していることを認識している。

• 探索空間： 彼らは、探索空間を商多様体 $\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])$ は測地線凸性を示すことができる。
• 等価性： 決定的なことに、商多様体上のリーマン勾配およびヘッセ行列は、水平空間に制限されたときの $\bar{h}(Y)$ のユークリッド勾配およびヘッセ行列と正確に一致する。これは、標準的な勾配降下アルゴリズム（ユークリッド空間上で動作するもの）が、この商多様体上のリーマン勾配降下法と計算上同一であることを意味しており、これにより著者らは幾何学的な保証を標準的なアルゴリズムへと転送することを可能にしている。

主要な貢献と結果

1. 多様体の幾何学的特性
著者らは、商多様体 $\mathcal{M}^q_{r+}$ の基本的な幾何学的特性を確立している：

• 測地線凸半径： $[Y]$ を中心とする測地線球において、半径 $x \leq \sigma_r(Y)/3$ は測地線凸であることを証明した。この半径は定数倍の範囲でシャープである。
• 意義： この結果は、ブラー・ワッサースタイン幾何学（$r=p$ の場合）における、ブラー・ワッサースタイン空間に対する初の明示的な測地線凸半径を提供するものである。

2. グローバルな景観解析（RSCおよびRSMの下で）
$f$ が $(2r, 4r)$-制限強凸性と滑らかさの性質を満たすとき、著者らは、分解された目的関数を3つの明確な領域に分類している（定理1、系1）：

• 領域 R1（ターゲットの近傍）： 真のパラメータの近傍において、目的関数 $h([Y])$ は測地線強凸かつ滑らかである。この領域は、真の解への距離が、条件数および最小特異値に対して小さいことによって定義される。
• 領域 R2（厳密な鞍点）： 厳密な鞍点の近傍では、リーマンヘッセ行列は少なくとも一つの負の固有値を持ち、明示的な脱出方向が提供される。
• 領域 R3（ターゲットから遠い領域）： 残りの領域では、リーマン勾配の大きさが大きい。

この「良質な景観（benign landscape）」構造（解の近傍での強凸性、鞍点での負の曲率、およびその他の場所での大きな勾配）は、ロバスト厳密鞍点特性（例：摂動付きリーマン勾配降下法）を満たすアルゴリズムが、グローバルな最小解へグローバルに収束することを保証する。

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$-精度を達成することを示す。

意義と主張
本論文は、リーマン商幾何学の下での、ブラー・モンテイロ分解された目的関数の初のグローバルな景観解析を提供すると主張している。その主な意義は以下の通りである：

• 幾何学的説明： ブラー・モンティアによる分解における素朴な勾配降下法の成功に対し、単なる局所的な正則性条件ではなく、商多様体上の目的関数の測地線強凸性に起因するという、完全な幾何学的説明を提供している。
• 汎用性： 結果は、最小二乗法だけでなく、RSC/RSMを満たす一般的な目的関数をカバーする、ノイズありおよびノイズなしの両方の設定を網羅している。
• シャープさ： 導出された凸半径（$\sigma_r(Y)/3$）は、定数倍を除いてシャープであることが示されている。
• アルゴリズムへの示唆： この解析は、勾配ベースの手法がなぜ不適切な局所解や鞍点を回避できるのかについて、理論的な基礎を提供し、その高速なグローバル収束を説明している。

著者らは、制限強凸性のパラメータ $\delta$ に関する条件が、最近の局所解析ほどシャープではない可能性があると述べているが、彼らの結果の幾何学的な性質（単なる正則性ではなく凸性を提供すること）は、アルゴリズムの性能に対するより直感的で堅牢な説明を提供するものである。また、過剰パラメータ化された設定における景観の探索や、測地線凸半径を最大化する計量の特定といった、今後の研究方向も提示している。