2025-11-10T03:06:05.923380

Revisit First-order Methods for Geodesically Convex Optimization

Shu, Jiang, Shi et al.

In a seminal work of Zhang and Sra, gradient descent methods for geodesically convex optimization were comprehensively studied. In particular, Zhang and Sra derived a comparison inequality that relates the iterative points in the optimization process. Since their seminal work, numerous follow-ups have studied different downstream usages of their comparison lemma. In this work, we introduce the concept of quasilinearization to optimization, presenting a novel framework for analyzing geodesically convex optimization. By leveraging this technique, we establish state-of-the-art convergence rates -- for both deterministic and stochastic settings -- under weaker assumptions than previously required. The technique of quasilinearization may prove valuable for other non-Euclidean optimization problems.

academic

測地凸最適化における一階法の再検討

基本情報

論文ID: 2504.06814
タイトル: Revisit First-order Methods for Geodesically Convex Optimization
著者: Yunlu Shu, Jiaxin Jiang, Lei Shi, Tianyu Wang（復旦大学）
分類: math.OC（数学最適化および制御）
発表日時: 2025年10月16日（arXiv v4版）
論文リンク: https://arxiv.org/abs/2504.06814

要約

本論文は、測地凸最適化における一階法を再検討する。ZhangとSraの先駆的研究では、測地凸最適化の勾配降下法を包括的に研究し、特に最適化プロセスにおける反復点の比較不等式を導出した。本論文では、準線形化（quasilinearization）の概念を最適化分野に導入し、測地凸最適化を分析するための新しい枠組みを提案する。この技術を活用することで、従来よりも弱い仮定条件の下で、決定論的および確率的設定の両方に対して最先端の収束率を確立する。準線形化技術は、他の非ユークリッド最適化問題にも価値を持つ可能性がある。

研究背景と動機

問題定義

本論文はHadamard多様体上の最適化問題を研究する： $\min_{x \in M} f(x)$ ここでMはリーマン計量gを備えたHadamard多様体である。

研究動機

既存方法の限界：ZhangとSraの古典的方法は2つの強い仮定に依存する：
- (A1) 断面曲率の一様下界（CBB条件）
- (A2) 軌跡直径の事前上界
実際的問題：多くの重要なHadamard多様体はCBB条件を満たさない。例えば、ワープ積多様体では曲率が負の無限大に近づく可能性がある。
中心的課題：仮定(A1)と(A2)を削除しながら、最先端の収束率を維持するにはどうするか？

中核的貢献

準線形化枠組みの導入：BergとNikolaevの準線形化概念を最適化問題分析に初めて適用
強い仮定の削除：曲率下界と有界領域の仮定なしに収束保証を確立
決定論的最適化：測地凸関数に対してO(1/t)収束率を実現
確率的最適化：滑らかな測地凸関数に対してÕ(1/√t)収束率を実現
理論的突破：質問(Q)に対する肯定的な答えを提供。すなわち、より弱い仮定の下で最適な収束率を維持できることを示す

方法の詳細

準線形化内積

多様体M上の任意の2つの順序付き測地線分 $\overrightarrow{xy}$ と $\overrightarrow{zw}$ に対して、準線形化内積は以下のように定義される：

$\langle\overrightarrow{xy}, \overrightarrow{zw}\rangle = |\overrightarrow{xy}||\overrightarrow{zw}|\cos_q(\overrightarrow{xy}, \overrightarrow{zw})$

ここで： $\cos_q(\overrightarrow{xy}, \overrightarrow{zw}) = \frac{|\overrightarrow{xw}|^2 + |\overrightarrow{yz}|^2 - |\overrightarrow{xz}|^2 - |\overrightarrow{yw}|^2}{2|\overrightarrow{xy}||\overrightarrow{zw}|}$

準凸性の定義

関数fがq-凸であるとは、以下を満たすことである： $f(x) \geq f(y) + \langle\overrightarrow{y\text{Exp}_y(\text{grad}f(y))}, \overrightarrow{yx}\rangle + \frac{\mu}{2}d^2(x,y)$

近接勾配アルゴリズム

中核的なアルゴリズムは暗黙的な近接更新を採用する： $x_t = \text{Exp}_{x_{t+1}}(\eta \text{grad}f(x_{t+1}))$

これは以下を解くことと等価である： $x_{t+1} = \arg\min_z \left\{f(z) + \frac{1}{2\eta}d(x_t, z)^2\right\}$

理論的分析

主要定理

定理1（決定論的場合）：fをHadamard多様体M上の測地凸関数とし、近接勾配アルゴリズムが以下を満たすとする： $f(x_t) - f(x^*) \leq \frac{|\overrightarrow{x_0x^*}|^2}{\eta t}$

定理2（確率的場合）：有界分散仮定の下で、ステップサイズ $\eta_t = \frac{1}{2L\sqrt{t}}$ を用いた確率的近接勾配アルゴリズムは以下を満たす： $\frac{1}{\sum_{t=1}^T \alpha_t}\sum_{t=1}^T \alpha_t(\mathbb{E}F(x_t) - F(x^*)) \leq \frac{|\overrightarrow{x_0x^*}|^2}{2\sum_{t=1}^T \alpha_t} + \frac{\sigma^2 \log(T+1)}{\sum_{t=1}^T \alpha_t}$