技術要約：決定論的な積分時間を用いたハミルトン力学による加速凸最適化

問題設定

本論文は、一次凸最適化の問題、具体的には勾配オラクル $\nabla f$ が利用可能な微分可能な凸関数 $f: \mathbb{R}^d \to \mathbb{R}$ の最小化を取り扱う。著者らは、滑らかな凸関数および $\alpha$-強凸目的関数の両方に対して、加速された収束率を達成することに焦点を当てている。

古典的な勾配降下法は、凸関数に対して $O(1/\epsilon)$、強凸関数に対して $O(\log(1/\epsilon))$ の収束率を達成するが、ネステロフの加速勾配法はこれらをそれぞれ $O(1/\sqrt{\epsilon})$ および $O(\sqrt{\kappa}\log(1/\epsilon))$ に改善する。近年の研究では、これら（加速されたレート）を連続時間の動的システム、特に二次の微分方程式を用いて導出しようとする試みがなされてきた。しかし、既存のハミルトン力学に基づく最適化手法には以下の制限があった：

1. 目的関数が二次形式であることを要求する場合が多い。
2. 一般的な凸関数に適用する場合、以前の保証（Fu and Wibisono, 2025など）は、ランダム化された積分時間にわたる期待値においてのみ成立する確率的なものであった。
3. 通常、軌道の終点に依存しており、特定の構造的仮定がない限り、一般的な凸関数に対して加速をもたらさない。

目標は、一般の滑らかな凸関数および強凸関数に対して、ランダム化や二次形式の仮定に頼ることなく、最適な一次複雑度を達成する決定論的なハミルトン力学ベースのアルゴリズムを開発することである。

手法

提案手法はハミルトン流 (Hamiltonian Flow: HF) を活用するが、最適化のためにその軌道をどのように利用するかという新しい視点を導入している。

1. ハミルトン力学の枠組み

著者らは、位相空間 $\mathbb{R}^{2d}$（位置 $X_t$ および速度 $Y_t$）におけるエネルギー関数：
$$H(x, y) = f(x) + \frac{1}{2}\|y\|^2$$
を持つハミルトン系を定義する。ダイナミクスは以下によって支配される：
$$\dot{X}_t = Y_t, \quad \dot{Y}_t = -\nabla f(X_t)$$
この系の重要な特性はエネルギー保存である：$f(X_t) + \frac{1}{2}\|Y_t\|^2 = f(X_0) + \frac{1}{2}\|Y_0\|^2$。もし $Y_0=0$ で初期化された場合、関数値 $f(X_t)$ は $f(X_0)$ を決して超えない。

2. 鍵となる洞察：平均化 vs 終点

本研究の主要な理論的貢献は、凸関数 $f$ に対して、ハミルトン軌道に沿った時間の平均化された位置が、軌道の終点よりも強力な降下保証を提供するという観察である。

• 補題 2 (Lemma 2) は、軌道の平均が最適性のギャップを収縮させることを示す微分不等式を確立している。
• 系 1 (Corollary 1) は、以下の通り定義される位置の特定の重み付き平均 $X_{\text{avg}}(X_0; T) = \frac{2}{T^2} \int_0^T (T-t)X_t dt$ が、収縮特性を満たすことを示している：
  $$f(X_{\text{avg}}) - f(z) + \frac{1}{3T^2}\|X_T - z\|^2 \leq \frac{2}{3}(f(X_0) - f(z)) + \frac{1}{3T^2}\|X_0 - z\|^2$$
  これは、積分時間 $T$ が適切に選択されている限り、最適性のギャップに対して普遍的な収縮因子 $2/3$ を持つことを意味する。

3. アルゴリズム設計

提案された洞察に基づき、2つのアルゴリズムを提案する：

• HFA (Hamiltonian Flow for optimization with Averaging): 理想化された連続時間アルゴリズム。現在のイテレートを位相空間へとリフトし、現在の時刻 $T_k$ まで正確なハミルトン流をシミュレートし、軌道の重み付き平均を計算し、オプションとしてこの平均と終点を混合して次のイテレートを形成する。

  • 強凸関数の場合、アルゴリズムは重み付き平均のみを使用する（$\lambda=0$）。
  • 凸関数の場合、二次的な成長の欠如に対処するため、平均と終点の混合を使用する（$\lambda=1$）。

• dHFA-eg (Discretized HFA with Extragradient): 実用的な離散時間実装。正確なHFのシミュレーションは一般に不可能であるため、著者らはエクストラグラディエント（外側勾配）インテグレータ（暗黙的インテグレータを近似する一次手法）を用いてフローを離散化する。

  • 連続的な積分は、離散的な重み付き和に置き換えられる。
  • アルゴリズムは同じ構造を維持する：$N_k$ ステップをシミュレートし、離散的な重み付き平均を計算し、最終的なイテレートと混合する。

主要な貢献

1. 平均化による決定論的な加速: 本論文は、ハミルトン力学ベースの手法が、一般の滑らかな凸関数および強凸関数に対して、決定論的に加速された収束率を達成できることを証明している。これは、期待値において同様のレートを得るためにランダム化された積分時間を必要とした先行研究（Fu and Wibisono, 2025）とは対照的である。
2. 新しい収縮補題: 著者らは、ハミルトン軌道の時間平均が最適性のギャップを因子 $2/3$（および残差項）で収縮させることを定式化した補題 2 および 系 1 を導出した。この特性は、一般的な凸目的関数に対してはこれまで確立されていなかった。
3. 最適な複雑度: 提案された離散アルゴリズム dHFA-eg は、ネステロフの加速勾配法と同じイテレーション複雑度を達成する：
   • 強凸: $O(\sqrt{\kappa} \log(1/\epsilon))$ の勾配評価。
   • 凸: $O(\sqrt{L/\epsilon})$ の勾配評価。
     ここで、$\kappa = L/\alpha$ は条件数である。
4. 実用的な離散化: 本研究は、勾配へのアクセスのみを必要とする（プロキシマル・オラクルを必要としない）エクストラグラディエント・インテグレータを利用することで、連続時間の動的システムと実装可能な一次手法との間の架け橋となる。

結果

論文は、提案されたアルゴリズムに対して厳密な理論的保証を提供している：

• 強凸の場合: $\alpha$-二次成長を満たす関数（$\alpha$-強凸性が含意する）に対して、一定の積分時間（または離散化ステップ）$T \propto 1/\sqrt{\alpha}$ で HFA (または dHFA-eg) を実行すると、幾何級数的な収束率が得られる。定理 1 および定理 3 は、誤差が $(2/3 + \delta)^K$ として減衰することを示し、最適な $O(\sqrt{\kappa} \log(1/\epsilon))$ の複雑度を導く。
• 凸の場合: 一般的な凸関数の場合、アルゴリズムは増加する積分時間 $T_k$（または離散化ステップ $N_k$）を必要とする。定理 2 および定理 4 は、ステップあたりのコストが増加するにもかかわらず、$\epsilon$-精度に達するための総複雑度が $O(1/\sqrt{\epsilon})$ であることを示している。
• 決定論的な保証: すべての収束境界は、期待値としてではなく、アルゴリズムのすべての実行に対して成立する。

意義と主張

著者らは、本研究が決定論的な加速凸最適化のための有用なアルゴリズム・プリミティブとしてのハミルトン力学を確立したと主張している。

• パラダイムシフト: 本研究は、「サンプリングを改善するために最適化のアイデアを用いる（サンプリングとしての最適化）」という視点から、「最適化を改善するためにサンプリングのアイデアを用いる（サンプリングのアイデアによる最適化）」という視点へと転換させている。
• 堅牢性: 二次形式の目的に限定されていたり、ランダム化を必要としたりした従来のハミルトンベースの最適化手法とは異なり、本アプローチは決定論的な保証とともに、一般の滑らかな凸関数に対して機能する。
• 理論的基礎: 本論文は、なぜ軌道の平均化が機能するのかを説明する新しい微分不等式（補題 2）を提供しており、連続時間のダイナミクスと離散加速手法との関係について、より深い理解を与えている。

著者らは、分析は凸関数に焦点を当てているものの、これらの手法は非凸最適化や加速サンプリング（HMC）にも影響を与える可能性があると述べているが、これらは今後の課題として残されている。本論文は、ネステロフの手法を漸近的な複雑度の面で上回ることを主張しているのではなく、むしろ、同じ最適なレートを決定論的に達成する、代替的なダイナミクスベースの導出を提供することを目指している。