關於基於採樣的可達性極限：幾何、動力學與樣本複雜度
本文研究了基於採樣的可達性分析中，初始集幾何形狀、動力學規律和採樣分佈對估計精度的影響。通過將問題建模為幾何支撐估計，作者發現兩個正則性質（初始集補集的正可達性和動力學的Lipschitz連續性）可使概率質量覆蓋保證提升為Hausdorff距離精度。樣本複雜度隨狀態維數和時間指數增長，且該指數依賴是本質的，無法通過算法改進消除。實驗驗證了對抗採樣可改善常數但無法改變縮放規律。
可達性分析是安全關鍵控制、機器學習和神經網絡驗證中的核心問題。傳統的哈密頓-雅可比可達性方法或集合傳播方法在高維狀態下計算複雜度極高。近年來，基於採樣的方法作為一種有前景的替代方案，能夠提供有限樣本保證，覆蓋未探索的概率質量。然而，現有文獻尚未系統揭示初始集的幾何形狀、動力學特性以及採樣分佈如何影響估計準確性。
本研究由Jixian Liu等四位作者完成，於2026年7月21日提交至arXiv。他們將基於採樣的可達集恢復問題重新詮釋為幾何支撐估計，針對由初始集、動力學和採樣規律定義的系列問題進行分析。首先，研究者識別出兩個關鍵的正則性質：初始集補集的正可達性（positive reach）和動力學的Lipschitz連續性。這兩個性質共同確保了恢復問題的適定性——即概率質量覆蓋保證可以升級為Hausdorff距離下的精度$r$。正可達性保證了初始集邊界的光滑性，而Lipschitz連續性則控制了狀態隨時間的演化扭曲程度。
其次，研究給出了樣本複雜度的上界：在$\tilde{\mathcal{O}}((e^{3LT}/r)^n)$個樣本下可實現恢復，其中$n$是狀態維數，$T$是時間範圍，$L$是Lipschitz常數。該複雜度對維數和時間均呈指數增長，這意味着在高維或長時間預測場景中，採樣方法需要天文數字的樣本才能達到較高精度。進一步，作者證明了極小極大下界$\Omega((e^{LT}/r)^n)$對所有估計器成立，表明指數依賴是固有的，而非特定方法的假象。這一下界意味着無論採用何種採樣策略或估計算法，指數縮放規律都無法突破。
最後，在非線性系統上的實驗表明，對抗採樣等方法可以改善常數因子，但無法改變指數縮放規律，驗證了理論結果的嚴格性。這一工作深刻揭示了採樣可達性問題的本質侷限：儘管採樣方法避免了經典方法的維度災難，但其自身同樣面臨指數增長的樣本複雜度，且這種複雜度來源於問題本身的幾何和動力學屬性，而非算法設計。因此，對於高維或長時間跨度的安全關鍵系統，純採樣方法可能無法滿足精度要求，未來需要結合其他技術（如模型降階或自適應採樣）來緩解這一根本性困難。