关于基于采样的可达性极限：几何、动力学与样本复杂度
本文研究了基于采样的可达性分析中，初始集几何形状、动力学规律和采样分布对估计精度的影响。通过将问题建模为几何支撑估计，作者发现两个正则性质（初始集补集的正可达性和动力学的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)$对所有估计器成立，表明指数依赖是固有的，而非特定方法的假象。这一下界意味着无论采用何种采样策略或估计算法，指数缩放规律都无法突破。
最后，在非线性系统上的实验表明，对抗采样等方法可以改善常数因子，但无法改变指数缩放规律，验证了理论结果的严格性。这一工作深刻揭示了采样可达性问题的本质局限：尽管采样方法避免了经典方法的维度灾难，但其自身同样面临指数增长的样本复杂度，且这种复杂度来源于问题本身的几何和动力学属性，而非算法设计。因此，对于高维或长时间跨度的安全关键系统，纯采样方法可能无法满足精度要求，未来需要结合其他技术（如模型降阶或自适应采样）来缓解这一根本性困难。