2025-11-21T05:43:14.438076

An Adaptive Algorithm for Bilevel Optimization on Riemannian Manifolds

Shi, Xiao, Jiang

Existing methods for solving Riemannian bilevel optimization (RBO) problems require prior knowledge of the problem's first- and second-order information and curvature parameter of the Riemannian manifold to determine step sizes, which poses practical limitations when these parameters are unknown or computationally infeasible to obtain. In this paper, we introduce the Adaptive Riemannian Hypergradient Descent (AdaRHD) algorithm for solving RBO problems. To our knowledge, AdaRHD is the first method to incorporate a fully adaptive step size strategy that eliminates the need for problem-specific parameters in RBO. We prove that AdaRHD achieves an $\mathcal{O}(1/Îµ)$ iteration complexity for finding an $Îµ$-stationary point, thus matching the complexity of existing non-adaptive methods. Furthermore, we demonstrate that substituting exponential mappings with retraction mappings maintains the same complexity bound. Experiments demonstrate that AdaRHD achieves comparable performance to existing non-adaptive approaches while exhibiting greater robustness.

academic

リーマン多様体上の二段階最適化のための適応的アルゴリズム

基本情報

論文ID: 2504.06042
タイトル: An Adaptive Algorithm for Bilevel Optimization on Riemannian Manifolds
著者: Xu Shi, Rufeng Xiao, Rujun Jiang (復旦大学データサイエンス学院)
分類: math.OC (最適化と制御)
発表会議: NeurIPS 2025 (第39回ニューラル情報処理システム会議)
論文リンク: https://arxiv.org/abs/2504.06042

要約

リーマン二段階最適化(RBO)問題を解くための既存の方法は、ステップサイズを決定するために問題の一階情報、二階情報、およびリーマン多様体の曲率パラメータを事前に知る必要があり、これらのパラメータが未知または計算不可能な場合に実用的な制限をもたらします。本論文では、RBO問題を解くための適応的リーマン超勾配降下法(AdaRHD)アルゴリズムを提案します。我々の知る限り、AdaRHDはRBOにおいて完全に適応的なステップサイズ戦略を採用した最初の方法であり、問題固有のパラメータへの依存性を排除しています。AdaRHDがε-定常点を見つけるためのO(1/ε)反復複雑度を達成することを証明し、これは既存の非適応的方法の複雑度と一致しています。さらに、指数写像を収縮写像で置き換えても同じ複雑度界が保たれることを証明しています。実験により、AdaRHDが既存の非適応的方法と同等の性能を得ながら、より強い堅牢性を示すことが示されました。

研究背景と動機

問題背景

二段階最適化問題は機械学習分野で広く応用されており、強化学習、メタラーニング、ハイパーパラメータ最適化、敵対的学習などが含まれます。リーマン二段階最適化(RBO)は、二段階最適化をリーマン多様体に拡張したもので、一般的な形式は以下の通りです:

$\min_{x \in \mathcal{M}_x} F(x) := f(x, y^*(x))$ $\text{s.t. } y^*(x) = \arg\min_{y \in \mathcal{M}_y} g(x,y)$

ここで $\mathcal{M}_x, \mathcal{M}_y$ はリーマン多様体、 $f,g$ は滑らかな関数、 $g(x,y)$ は $y$ に関して測地強凸です。

既存方法の限界

パラメータ依存性：既存のRBO方法(RHGD、RieBO等)は、ステップサイズを決定するために強凸パラメータ、リプシッツ定数、曲率パラメータなどを事前に知る必要があります
実用性の制限：これらのパラメータは実際の応用では推定が困難であるか、計算コストが高すぎます
堅牢性の不足：固定ステップサイズ戦略は初期化と問題の条件数に敏感です

研究動機

本論文の核心的な動機は、以下を実現できる完全に適応的なRBOアルゴリズムを設計することです:

問題固有のパラメータを事前に知る必要がない
ステップサイズを自動的に調整して問題特性に適応する
非適応的方法と同等の理論的複雑度を保つ
より強い実用的堅牢性を提供する

核心的貢献

最初の適応的RBOアルゴリズム：AdaRHDを提案。これはリーマン二段階最適化において完全に適応的なステップサイズ戦略を採用した最初のアルゴリズムであり、強凸性、リプシッツ定数、曲率パラメータへの依存性を排除しています
理論的複雑度の一致：AdaRHDがε-定常点を見つけるためのO(1/ε)反復複雑度を達成することを証明し、既存の非適応的方法の複雑度と一致しています
収縮写像への拡張：計算効率がより高い収縮写像で指数写像を置き換えても同じ複雑度保証が保たれることを証明しています
実験検証：複数のRBO問題上でアルゴリズムの有効性と堅牢性を検証。リーマン超表現学習と堅牢最適化問題を含みます

方法の詳細

タスク定義

リーマン二段階最適化問題を考えます:

上層問題：多様体 $\mathcal{M}_x$ 上で $F(x) = f(x, y^*(x))$ を最小化
下層問題：与えられた $x$ に対して、多様体 $\mathcal{M}_y$ 上で $y^*(x) = \arg\min_y g(x,y)$ を求解
制約： $g(x,y)$ は $y$ に関して測地強凸、 $f$ は凸性を要求しない

核心技術：リーマン超勾配

リーマン超勾配は以下のように定義されます: $G_F(x) = G_x f(x, y^*(x)) - G^2_{xy}g(x, y^*(x))[H^{-1}_y g(x, y^*(x))[G_y f(x, y^*(x))]]$

正確な計算が困難なため、近似リーマン超勾配を使用します: $\hat{G}_F(x, \hat{y}, \hat{v}) = G_x f(x, \hat{y}) - G^2_{xy}g(x, \hat{y})[\hat{v}]$

ここで $\hat{y}$ は下層問題の近似解、 $\hat{v}$ は線形系の近似解です。

AdaRHDアルゴリズムの構造

アルゴリズム1：AdaRHDの主要ステップ

下層問題の求解：適応的勾配降下法を使用
- ステップサイズ更新： $b^2_{k+1} = b^2_k + \|G_y g(x_t, y^k_t)\|^2$
- 反復更新： $y^{k+1}_t = \text{Exp}_{y^k_t}(-\frac{1}{b_{k+1}} G_y g(x_t, y^k_t))$
線形系の求解：2つの戦略
- 勾配降下法：下層問題と同様の適応的ステップサイズ
- 共役勾配法：接空間共役勾配法を使用
上層更新：適応的超勾配降下法
- ステップサイズ更新： $a^2_{t+1} = a^2_t + \|\hat{G}_F(x_t, y^{K_t}_t, v^{N_t}_t)\|^2$
- 反復更新： $x_{t+1} = \text{Exp}_{x_t}(-\frac{1}{a_{t+1}} \hat{G}_F(x_t, y^{K_t}_t, v^{N_t}_t))$

技術的革新点

累積勾配ノルム戦略：「累積リーマン勾配ノルムの逆数」を適応的ステップサイズとして採用し、問題パラメータの事前知識を不要にします
三層適応性：上層、下層、線形系に対してすべて適応的ステップサイズを採用し、完全な適応的フレームワークを形成します
収縮写像の最適化：指数写像を収縮写像で置き換えるバージョンを提供し、計算複雑度を低減します
理論的保証：厳密な収束分析。リーマン多様体の幾何学的構造がもたらす技術的課題に対応しています

実験設定

データセットと問題

単純行列相似性問題：Stiefel多様体とSPD多様体上の最適化
- データ規模：n=100およびn=1000
- パラメータ設定：d=50, r=20, λ=0.01
深層超表現学習：AFEW感情認識データセット
- 3層SPDネットワークアーキテクチャ
- 7つの感情カテゴリ、1747個の訓練サンプル
- 不均衡なクラス分布
堅牢最適化問題：
- 堅牢Karcher平均問題
- 堅牢最尤推定問題