サンプリングベースの到達可能性の限界：幾何学、ダイナミクス、サンプル複雑性
本論文では、サンプリングベースの到達可能性解析において、初期集合の幾何形状、ダイナミクス、サンプリング分布が推定精度に与える影響を調査する。問題を幾何学的サポート推定として定式化し、初期集合の補集合の正のリーチとダイナミクスのリプシッツ連続性という2つの正則性条件を特定する。これにより、確率質量カバレッジ保証をハウスドルフ距離精度に昇格できる。サンプル複雑性は状態次元と時間に指数関数的に増加し、この指数依存性は本質的である。非線形システムの実験により、敵対的サンプリングは定数を改善するがスケーリングは変えないことが確認された。
到達可能性解析は、安全クリティカルな制御、ロボティクス、ニューラルネットワーク検証において中心的な問題です。従来のハミルトン-ヤコビ到達可能性や集合伝播手法は、状態次元が高くなると計算複雑性が急増します。近年、サンプリングベースの手法が有望な代替手段として登場し、有限サンプルで未カバーの確率質量を抑える保証を提供します。しかし、初期集合の幾何形状、ダイナミクス特性、サンプリング分布が推定精度にどのように影響するかは、文献で完全には明らかにされていません。
本研究は、Jixian Liuら4名の著者によって2026年7月21日にarXivに提出されました。彼らはサンプリングベースの到達可能集合回復を、初期集合、ダイナミクス、サンプリング則で定義された問題族に対する幾何学的サポート推定として再定式化します。まず、初期集合の補集合の正のリーチ（positive reach）とダイナミクスのリプシッツ連続性という二つの正則性条件を特定します。これらにより、問題の適切性が保証され、確率質量カバレッジ保証がハウスドルフ距離での精度$r$に昇格できます。正のリーチは初期集合の境界の滑らかさを保証し、リプシッツ連続性は状態の時間発展による歪みを制御します。
次に、サンプル複雑性の上界を導出します：回復には$\tilde{\mathcal{O}}((e^{3LT}/r)^n)$サンプルが必要で、状態次元$n$と時間領域$T$に指数関数的に依存します。このことは、高次元や長時間予測のシナリオでは、高い精度を達成するために天文学的なサンプル数が必要となることを意味します。さらに、任意の推定器に対して最小最大下界$\Omega((e^{LT}/r)^n)$が成り立つことを示し、次元と時間への指数依存性が本質的であり、特定の手法の人為的成果ではないことを証明します。この下界は、サンプリング戦略や推定アルゴリズムをどのように変更しても、指数スケーリング則を突破できないことを示しています。
最後に、非線形システムを用いた実験では、敵対的サンプリングにより定数因子は改善されるものの、指数スケーリング則は変わらないことが確認され、理論結果を裏付けています。この研究は、サンプリング到達可能性問題の本質的な限界を明らかにしました。サンプリング手法は古典的手法の次元の呪いを回避しますが、それ自体が指数関数的サンプル複雑性に直面しており、この複雑性は問題自体の幾何学的・動的特性に起因するもので、アルゴリズム設計によるものではありません。したがって、高次元や長時間の安全クリティカルシステムでは、純粋なサンプリング手法では要求精度を満たせない可能性があり、将来はモデル低次元化や適応的サンプリングなどの技術と組み合わせて根本的困難を緩和する必要があります。