2025-11-17T22:04:13.678417

A Stochastic Algorithm for Searching Saddle Points with Convergence Guarantee

Shi, Zhang, Du

Saddle points provide a hierarchical view of the energy landscape, revealing transition pathways and interconnected basins of attraction, and offering insight into the global structure, metastability, and possible collective mechanisms of the underlying system. In this work, we propose a stochastic saddle-search algorithm to circumvent exact derivative and Hessian evaluations that have been used in implementing traditional and deterministic saddle dynamics. At each iteration, the algorithm uses a stochastic eigenvector-search method, based on a stochastic Hessian, to approximate the unstable directions, followed by a stochastic gradient update with reflections in the approximate unstable direction to advance toward the saddle point. We carry out rigorous numerical analysis to establish the almost sure convergence for the stochastic eigenvector search and local almost sure convergence with an $O(1/n)$ rate for the saddle search, and present a theoretical guarantee to ensure the high-probability identification of the saddle point when the initial point is sufficiently close. Numerical experiments, including the application to a neural network loss landscape and a Landau-de Gennes type model for nematic liquid crystal, demonstrate the practical applicability and the ability for escaping from "bad" areas of the algorithm.

academic

鞍点探索のための確率的アルゴリズムと収束保証

基本情報

論文ID: 2510.14144
タイトル: A Stochastic Algorithm for Searching Saddle Points with Convergence Guarantee
著者: Baoming Shi (コロンビア大学), Lei Zhang (北京大学), Qiang Du (コロンビア大学)
分類: math.NA, cs.NA (数値解析)
発表日: 2024年10月15日
論文リンク: https://arxiv.org/abs/2510.14144

要旨

鞍点はエネルギーランドスケープに階層的な視点を提供し、遷移経路と相互接続された吸引盆を明らかにすることで、システムの全体構造、準安定性、および可能な集団メカニズムの理解に洞察を与えます。本論文は、従来の確定的鞍点動力学における正確な導関数とヘッシアン行列の評価を回避する確率的鞍点探索アルゴリズムを提案しています。このアルゴリズムは、各反復で確率的ヘッシアンに基づく確率的固有ベクトル探索法を使用して不安定方向を近似し、その後、近似不安定方向での反射を通じた確率的勾配更新により鞍点に向かって進みます。著者らは厳密な数値解析を実施し、確率的固有ベクトル探索のほぼ確実な収束性と鞍点探索の局所的ほぼ確実な収束性(収束率O(1/n))を確立し、初期点が十分に近い場合に高確率で鞍点を識別するための理論的保証を提供しています。

研究背景と動機

問題背景

鞍点探索は複数の科学分野において重要な意義を持ちます:

材料科学と化学: 相転移における臨界核形成と遷移経路の理解
液晶物理: 欠陥配置の分析
生物学: タンパク質折り畳み研究
深層学習: ニューラルネットワーク損失ランドスケープ分析

既存手法の限界

従来の鞍点探索アルゴリズムは主に2つのカテゴリに分類されます:

経路探索法: 文字列法など、最小エネルギー経路を探索
表面歩行法: 最穏勾配上昇動力学、ダイマー法、高指標鞍点動力学(HiSD)

これらの手法の主な限界は以下の通りです:

勾配とヘッシアン行列の正確な計算が必要で、計算コストが高い
特定の応用では勾配/ヘッシアンが利用不可能または取得困難
確率的版の厳密な理論解析が不足している

研究動機

本論文は、以下を実現できる確率的鞍点探索アルゴリズムの開発を目指しています:

正確な導関数とヘッシアン評価を回避する
厳密な収束性理論保証を提供する
実際の応用において良好な性能と逃脱能力を発揮する

核心的貢献

初めて提案: 収束保証を伴う確率的鞍点探索アルゴリズム、この分野の理論解析の空白を埋める
完全な理論フレームワークの確立:
- 確率的固有ベクトル探索のほぼ確実な収束性
- 鞍点探索の局所的ほぼ確実な収束性、収束率O(1/n)
- 高確率収束の理論保証
複数の収束性結果の提供:
- 既知不安定空間の場合の全体収束
- 未知不安定空間の場合の局所収束
- 非精密固有ベクトルの場合の収束分析
アルゴリズムの実用性の検証: ニューラルネットワーク損失ランドスケープと液晶モデルなどの実際の応用を通じた効果の実証

方法の詳細

タスク定義

目的関数 $f(x): \mathbb{R}^d \to \mathbb{R}$ が与えられたとき、そのindex-k鞍点 $x^*$ を探索します。これは以下を満たします:

$\nabla f(x^*) = 0$
$\nabla^2 f(x^*)$ はk個の負固有値と(d-k)個の正固有値を持つ

アルゴリズムアーキテクチャ

1. 不安定空間が既知の場合

凸-凹構造の問題に対して: $\min_{x_{V^⊥} \in V^⊥} \max_{x_V \in V} f(x_V + x_{V^⊥})$

確率的鞍点動力学は: $\begin{cases} x_V(n+1) = x_V(n) + \alpha(n)P_V\nabla f(x_V(n) + x_{V^⊥}(n);\omega(n)) \\ x_{V^⊥}(n+1) = x_{V^⊥}(n) - \alpha(n)(I-P_V)\nabla f(x_V(n) + x_{V^⊥}(n);\omega(n)) \end{cases}$