論文の概要: On the Limits of Sampling-Based Reachability: Geometry, Dynamics, and Sample Complexity
- arxiv url: http://arxiv.org/abs/2607.18606v1
- Date: Tue, 21 Jul 2026 00:54:27 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-22 19:05:05.285706
- Title: On the Limits of Sampling-Based Reachability: Geometry, Dynamics, and Sample Complexity
- Title（参考訳）: サンプリングに基づく到達可能性の限界について:幾何, ダイナミクス, サンプル複雑度
- Abstract要約: 我々は,初期セットで指定された問題群に対する幾何的支援推定として,サンプリングベースリーチブル・セット・リカバリをキャストした。
ミニマックス下限の$big((eLT/r)nbig)$ hold for every estimator。
非線形系の実験では、対向サンプリングは定数を改善するがスケーリングはしないことを確認した。
- 参考スコア（独自算出の注目度）: 3.9945187423832507
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Reachability analysis is central to safety-critical control, robotics, and neural network verification, but classical computational methods, such as Hamilton--Jacobi reachability and set propagation, scale poorly with state dimension. Sampling-based methods have emerged as a promising alternative, often providing finite-sample guarantees that bound the probability-mass left uncovered. However, an explicit account of how the geometry of the initial set, the dynamics, and the sampling law affect the accuracy of the estimator is not fully available in the literature. We study this by casting sampling-based reachable-set recovery as geometric support estimation over a family of problems specified by an initial set, its dynamics, and a sampling law. First, we identify two regularity properties, positive reach of the initial set's complement and Lipschitz continuity of the dynamics, that together make recovery well-posed: a probability-mass coverage guarantee can be upgraded to accuracy $r$ in Hausdorff distance. Second, we bound the resulting sample complexity: recovery is achievable with $\tilde{\mathcal{O}}\big((e^{3LT}/r)^n\big)$ samples, exponential in both the state dimension and the time horizon. Third, we show that neither can be removed: an minimax lower bound of $Ω\big((e^{LT}/r)^n\big)$ holds for every estimator, so the exponential dependence on dimension and the degradation over the horizon are both intrinsic, not artifacts of a particular method. Experiments on nonlinear systems confirm that adversarial sampling improves constants but not the scaling.
- Abstract（参考訳）: 到達可能性解析は、安全クリティカルな制御、ロボティクス、ニューラルネットワーク検証の中心であるが、ハミルトン-ヤコビの到達可能性やセットの伝播といった古典的な計算手法は、状態次元に劣る。
サンプリングベースの手法は有望な代替手段として現れており、しばしば有限サンプル保証を提供し、未発見の確率質量を束縛する。
しかし、初期集合の幾何、力学、サンプリング法則が推定器の精度にどのように影響するかという明確な説明は、文献で完全には得られない。
本研究は, 初期値, 動的値, サンプリング法則によって規定される問題群に対する幾何的支援推定として, サンプリングベースリーチブル・セット・リカバリをキャストすることで検討する。
まず、初期集合の補集合の正のリーチと力学のリプシッツ連続性という2つの正則性を見極め、共に回復をうまく立証する:確率質量被覆保証はハウスドルフ距離において精度$r$にアップグレードできる。
回復は$\tilde{\mathcal{O}}\big((e^{3LT}/r)^n\big)$サンプルで達成できる。
第3に、すべての推定器に対して$Ω\big((e^{LT}/r)^n\big)$のミニマックス下界が成り立つので、次元への指数的依存と地平線上の分解はどちらも本質的であり、特定の方法の人工物ではない。
非線形系の実験では、対向サンプリングは定数を改善するがスケーリングはしないことを確認した。
関連論文リスト
- Convex Basins in Single-Index Model Loss Landscapes: Applications to Robust Recovery under Strong Adversarial Corruption [4.52430575477004]
本研究では,重み付き雑音の存在下で,ガウス単体指数モデル(SIM)を頑健に学習する問題について検討する。
一般単調なリンク関数に対して、線形に近いサンプルと時間的複雑さを持つ最初のロバストなリカバリアルゴリズムを提案する。
論文 参考訳（メタデータ） (2026-05-28T07:21:04Z) - Fitting Unknown Number of Hyperplanes with Manifold Optimization [57.48093263119306]
未知数の線形平面をデータに適合させることは、機械学習の根本的な課題である。
既存のアプローチはしばしば最適な最適化に苦しむか、幾何的整合性に欠ける。
論文 参考訳（メタデータ） (2026-05-27T14:02:20Z) - Coverage Analysis of Rydberg Atom Quantum Receiver Arrays: A Stochastic Geometry Approach [55.47164192369501]
ライドバーグ原子量子受信機(RAQR)は、量子制限感度とブロードバンドチューナビリティを提供する。
密集した展開において、集合的干渉は原子トランスデューサを小さな信号状態から外すことができる。
本稿では、RAQRフロントエンドを幾何学的カバレッジ分析に埋め込むことで、この問題に対処する。
論文 参考訳（メタデータ） (2026-05-22T04:05:13Z) - Dual-space posterior sampling for Bayesian inference in constrained inverse problems [5.739708455652395]
偏微分方程式によって制約される逆問題はしばしば、ノイズや不完全データ、あるいは固有の非特異性によって不等式化される。
本研究では,波動方程式などの厳密な物理的制約を,既存のサンプリング手法に適合する事前分布に翻訳する手法を開発した。
論文 参考訳（メタデータ） (2026-02-28T00:34:31Z) - Analysis of Hessian Scaling for Local and Global Costs in Variational Quantum Algorithm [0.42970700836450487]
変分量子アルゴリズムにおけるヘッセンのエントリーワイズ解の定量化を行う。
ショットノイズに対してヘッセン成分を解くのに必要なサンプルの複雑さを規定する2つの異なるスケーリング機構を示す。
論文 参考訳（メタデータ） (2026-01-31T15:49:23Z) - Phase-space entropy at acquisition reflects downstream learnability [54.4100065023873]
楽器分解位相空間に基づく取得レベルスカラー$S_mathcal B$を提案する。
本稿では, (S_mathcal B) が周期サンプリングの位相空間コヒーレンスを正確に同定できることを理論的に示す。
$|S_mathcal B|$は一貫してサンプリングジオメトリをランク付けし、トレーニングなしで下流での再構築/認識の困難を予測します。
論文 参考訳（メタデータ） (2025-12-22T10:03:51Z) - Assessing One-Dimensional Cluster Stability by Extreme-Point Trimming [0.0]
本研究では, 一次元試料のテール挙動と幾何学的安定性を評価するための確率的手法を開発した。
有限サンプル補正を含む解析式は、一様仮説とガウス仮説の両方の下で期待される縮退について導出する。
我々はさらにクラスタリングパイプライン(DBSCANなど)に統合し、密度推定やパラメータチューニングなしに1次元のクラスタを検証する能力を示す。
論文 参考訳（メタデータ） (2025-08-29T21:52:15Z) - A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。
本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
論文 参考訳（メタデータ） (2024-04-29T15:04:07Z) - The Generalized Lasso with Nonlinear Observations and Generative Priors [63.541900026673055]
我々は、幅広い測定モデルで満たされるガウス下測度を仮定する。
この結果から, 局所埋込特性を仮定して, 均一回復保証まで拡張できることが示唆された。
論文 参考訳（メタデータ） (2020-06-22T16:43:35Z) - The Simulator: Understanding Adaptive Sampling in the
Moderate-Confidence Regime [52.38455827779212]
エミュレータと呼ばれる適応サンプリングを解析するための新しい手法を提案する。
適切なログファクタを組み込んだトップk問題の最初のインスタンスベースの下位境界を証明します。
我々の新しい分析は、後者の問題に対するこの種の最初のエミュレータであるベストアームとトップkの識別に、シンプルでほぼ最適であることを示した。
論文 参考訳（メタデータ） (2017-02-16T23:42:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。