効率的な非凸サンプリングの幾何学

arXiv stat.ML / 2026/3/27

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

共有:

要点

本論文は、高次元空間における任意のコンパクト集合から「ウォームスタート」状態を起点として、一様サンプリングを行うための多項式時間アルゴリズムを導入する。
アイソパリメトリ（等周）に基づく条件と、自然な体積成長性により、効率的な非凸サンプリングが可能になることを示す。
理論的保証は、凸集合や星形集合に対して知られている先行のサンプリング結果を一般化する、広範な統一として位置づけられている。
アルゴリズムの計算量は、次元、集合上の一様分布のポアンカレ定数、そして集合の体積成長定数に依存する。
本研究は、非凸幾何における効率的サンプリングの数学的基盤に焦点を当てており、その成果は下流の確率的推論や最適化手法を支える可能性がある。

抽象: 我々は、アイソパリメトリ条件と自然な体積成長条件のもとで、ウォームスタートから任意のコンパクトな体 $\mathcal{X} \subset \mathbb{R}^n$ を一様にサンプリングするための効率的なアルゴリズムを提示する。本結果は、凸体および星形体に対する既知の結果に対する、実質的な共通の一般化を与える。アルゴリズムの計算量は、次元、体 $\mathcal{X}$ 上の一様分布のポアンカレ定数、および集合 $\mathcal{X}$ の体積成長定数に関して多項式である。