Potential Hessian Ascent IV: Sampling the Sherrington-Kirkpatrick model at $\beta < 1$

技術要約：潜在的なヘッセ行列の上昇 IV：$\beta < 1$ におけるシャーロット・カークパトリック・モデルのサンプリング

問題設定
本論文は、シャーロット・カークパトリック（SK）スピングラス・モデルのギブス測度からのサンプリングに関する計算問題に取り組んでいる。このモデルは、サイズ $n$ のシステム、ランダムな対称行列 $A \sim \text{GOE}(n)$、および逆温度 $\beta$ によって定義される。目標は、全変動距離（TVD）誤差が $n \to \infty$ において消失する（すなわち $o_n(1)$ となる）ような、ギブス分布 $\mu_{\beta A}$ からのサンプルを生成する多項式時間のアルゴリズムを設計することである。

著者らによる先行研究 [DLSS26a] では、$\beta < 1/2$ においてこれが達成された。しかし、$\beta > 1/2$（具体的には $0.798 < \beta < 1$ の範囲）では、TAP（Thouless-Anderson-Palmer）自由エネルギーがグローバルに強凸ではないことが知られている。このグローバルな凸性の欠如は、以前のアルゴリズム的確率局在化（ASL）解析で必要とされていた、グローバルなリプシッツ連続性および滑らかさの仮定（TAP ヘッセ行列の逆行列、すなわちレゾルベントに関するもの）を崩してしまう。$\beta < 1$ のレジームは、システムがフル・レプリカ対称性の破れ（fRSB）を示す $\beta > 1$ の境界として、計算量的に困難な閾値であると考えられている。

手法
著者らは、グローバルな正則性の要件を、確率過程の尤もらしい軌道付近での局所的な正則性へと置き換えることで、以前の ASL フレームワークを拡張している。コアとなる手法は以下の通りである：

1. 拒絶サンプリングを伴うアルゴリズム的確率局在化 (ASL): アルゴリズムは $dy_t = m_t dt + dB_t$ という ASL プロセスに従うが、磁化 $m_t$ を近似するために TAP 自由エネルギーを利用する。極めて重要な点として、アルゴリズムには拒絶ステップが含まれる。もし軌道が、TAP ヘッセ行列が局所的に強凸となる「安全集合」 $S_{\beta, A}(c)$ を離れた場合、その軌道は破棄され、再試行される。
2. 生存を伴うジャルジンスキー等式 (JE): 拒絶サンプリング（安全集合を離れた時点でプロセスを停止させること）によって導入されるバイアスを補正するために、著者らは修正されたジャルジンスキー等式を導出している。これにより、生存したパスに対して重み付けを行い、ターゲットとなる分布を近似することが可能になる。
3. Celentano の結果による局所強凸性: 安全集合の存在は、$\beta < 1$ において TAP 自由エネルギーが近似メッセージパッシング（AMP）のイテレートの周囲の小さな球内で局所的に強凸であることを証明した Celentano [Cel24] の結果を用いて確立される。著者らは、確率局在化下での SK モデルの安定性（[AMS22] より）と組み合わせることで、ASL の軌道が高確率でこれらの局所凸領域内に留まることを示す。
4. レゾルベント解析と正則化: 安全集合の非凸性と、その外部における TAP ヘッセ行列の潜在的な特異性を扱うため、著者らはレゾルベント（TAP ヘッセ行列の逆）の $C^2$ 正則化を導入している。彼らは、レゾルベントの二乗の対角成分を制御するために、自由確率論の手法と、ブロック行列表現（[BBv23] に着想を得たもの）を利用し、一様な集中不等式を確立している。
5. リプシッツ拡張: 安全集合は凸ではないため、直線に沿った標準的な微分境界は適用できない。著者らは、安全集合内での短い経路を構築し、レゾルベント恒等式を用いて、グローバルな凸性に依存することなく、ドリフト係数、拡散係数、および JE 重みの被積分関数に対するリプシッツ境界を導出する。

主な貢献

• $\beta < 1$ への拡張: 固定された $\beta < 1$ に対して SK モデルの多項式時間サンプリングアルゴリズムを提供し、以前の $\beta < 1/2$ の障壁を打破した。
• 局所正則性フレームワーク: グローバルな正則性の要件を、安全集合上の局所的な正則性へと緩和する「デシデラタ（要件）」を定式化した。このフレームワークは、ASL-JE 解析にはこれで十分であることを示している。
• ハイブリッド凸性証明: AMP イテレートに対する Celentano の局所凸性結果と、確率局在化（SL）の安定性を組み合わせることで、TAP ヘッセ行列が全確率局在化パスにわたって一様に局所的に強凸であることを証明した。
• 洗練されたレゾルベント解析: 正則化されたレゾルベント拡張を導入し、テンソル積や共分散構造に関連する従来の技術的ボトルネックを回避するため、ブロック行列表現を用いた簡略化された自由補間議論を用いて、レゾルベントの対角成分を制御した。
• 拒絶サンプリング解析: 「生存に基づく」ジャルジンスキー等式を用いた拒絶サンプリングの厳密な解析を提供し、軌道を破棄することによる誤差が $o_n(1)$ であることを保証した。

結果
本論文は 定理 1.1 を確立している：任意の固定された $0 < \beta < 1$ および $\delta > 0$ に対して、すべての $n \geq n_0$ なる $n$ について、無秩序 $A$ に関する確率が少なくとも $1-\delta$ で、提案されたアルゴリズム（Algorithm 2）は、ギブス測度 $\mu_{\beta A}$ と TVD で $o_n(1)$ 近い分布からのサンプルを多項式時間で出力する。

解析は、更新されたデシデラタの検証に基づいている：

• (d1) 共分散推定誤差が有界であること。
• (d2a) TAP ヘッセ行列が SL パスに沿って一様に局所的に強凸であること。
• (d2b) TAP ヘッセ行列が局所的な正則性（レーヴェン・サンドイッチ）境界を満たすこと。
• (d3)-(d5) ドリフト、拡散、および JE 重みの項が、安全集合上で必要なリプシッツ連続性と誤差境界を満たすこと。

意義
本論文は、SK モデルにおいて（$\beta < 1$ の）de Almeida-Thouless (dAT) 線以下でグラウバー動力学が高速混合するという予想を解決するための重要な一歩であると主張している。ASL が局所的な正則性と拒絶サンプリングを通じてグローバルな凸性の障壁を回避できることを示すことで、本研究は、グローバルな関数不等式の確立が困難なスピングラス・モデルにおけるサンプリングへの新しい経路を提供している。著者らは、最終的なサンプリングの保証を得るために、ASL を局在化された分布の高速混合結果（[KSTZ26] による）と組み合わせている。

また、本アプローチにとって $\beta < 1$ のレジームが鋭い境界であることを強調している。なぜなら、$\beta > 1$ では、安定したアルゴリズム（ASL を含む）が $W_2$ 距離を小さくしてサンプリングすることは不可能であり、最悪ケースのグラウバー動力学は指数関数的に遅い混合を示すことが知られているからである。本論文は $\beta \geq 1$ のサンプリング問題を解決したり、グラウバー動力学の高速混合を直接証明したりすることを目的としているのではなく、計算量的な閾値とされる高温レジームにおけるギブス測量の効率的なサンプラーを提供している。