In-and-Out：凸体のサンプリングのためのアルゴリズム的拡散

arXiv stat.ML / 2026/3/23

💬 オピニオンIdeas & Deep AnalysisModels & Research

共有:

要点

この論文は、高次元の凸体から点を一様にサンプリングするための新しいランダムウォークアルゴリズムを提案する。
実行時間の計算量に関して最先端の性能を主張しつつ、Rényiダイバージェンスによって測られる、より強い統計的保証を与えることを示す。その保証はさらに、全変動距離（total variation）、Wasserstein-2、KLダイバージェンス、カイ二乗距離（chi-squared distance）の上界にもつながる。
換算（収束）解析では、新しい「確率的拡散（stochastic diffusion）」という観点を用い、目標分布へ向けた収縮（contraction）を示す。
収束率は、目標分布の関数的等周（isoperimetric）定数によって特徴づけられ、先行する多項式時間のサンプリング手法と比べて洗練された理論的見通しを提供する。
本研究は凸体サンプリングに関する理論的進展として位置づけられており、高次元のアルゴリズム的パイプラインにおけるサンプリング下位ルーチンの挙動を改善しうる可能性がある。

概要: 高次元の凸体を一様にサンプリングするための新しいランダムウォークを提示します。これは、従来までに知られていたものよりも出力に対するより強い保証を備えつつ、最先端の計算時間計算量を達成します。すなわち、R\'enyiダイバージェンス（これにより、TV、 $\mathcal{W}_2$ 、KL、 $\chi^2$ が含意されます）においてです。この証明は、本問題に対する多項式時間アルゴリズムの既知のアプローチから離れています。私たちは、確率的拡散の観点を用いて、目標分布に対する収縮を示し、その収束率が目標分布の汎関数等周定数によって決まることを明らかにします。