論文の概要: Improved Sample Complexity for Full Coverage in Compact and Continuous Spaces

• arxiv url: http://arxiv.org/abs/2511.17784v1
• Date: Fri, 21 Nov 2025 21:06:14 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-25 18:34:24.425149
• Title: Improved Sample Complexity for Full Coverage in Compact and Continuous Spaces
• Title（参考訳）: コンパクト・連続空間における全被覆試料の複素性の改善
• Authors: Lyu Yuhuan,
• Abstract要約: 我々は$d$次元単位ハイパーキューブにおける一様ランダムサンプリングについて検討した。 故障確率に対数依存するサンプル複雑性を導出する。 我々の発見は、グリッドベースのカバレッジ保証に依存するアルゴリズムに対して、よりシャープな理論的ツールを提供する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Verifying uniform conditions over continuous spaces through random sampling is fundamental in machine learning and control theory, yet classical coverage analyses often yield conservative bounds, particularly at small failure probabilities. We study uniform random sampling on the $d$-dimensional unit hypercube and analyze the number of uncovered subcubes after discretization. By applying a concentration inequality to the uncovered-count statistic, we derive a sample complexity bound with a logarithmic dependence on the failure probability ($δ$), i.e., $M =O( \tilde{C}\ln(\frac{2\tilde{C}}δ))$, which contrasts sharply with the classical linear $1/δ$ dependence. Under standard Lipschitz and uniformity assumptions, we present a self-contained derivation and compare our result with classical coupon-collector rates. Numerical studies across dimensions, precision levels, and confidence targets indicate that our bound tracks practical coverage requirements more tightly and scales favorably as $δ\to 0$. Our findings offer a sharper theoretical tool for algorithms that rely on grid-based coverage guarantees, enabling more efficient sampling, especially in high-confidence regimes.
• Abstract（参考訳）: ランダムサンプリングによる連続空間上の均一条件の検証は、機械学習と制御理論において基本的なものであるが、古典的カバレッジ分析はしばしば保守的な境界、特に小さな故障確率をもたらす。 我々は,$d$次元単位ハイパーキューブについて一様ランダムサンプリングを行い,離散化後の未発見サブキューブ数を解析した。 未知数統計量に濃度不等式を適用することにより、失敗確率(δ$)、すなわち$M = O( \tilde{C}\ln(\frac{2\tilde{C}}δ))$の対数依存に結びついたサンプル複雑性を導出する。 標準的なリプシッツと均一性の仮定の下では、自己完結した導出を示し、その結果を古典的なクーポン・コレクタレートと比較する。 次元、精度レベル、信頼度目標にわたる数値的な研究は、我々の有界トラックが実用的なカバレッジ要件をより厳密に追跡し、$δ\to 0$と好意的にスケールすることを示している。 我々の発見は、グリッドベースのカバレッジ保証に依存し、特に高信頼体制においてより効率的なサンプリングを可能にするアルゴリズムに対して、よりシャープな理論的ツールを提供する。

関連論文リスト

• Convergence, design and training of continuous-time dropout as a random batch method [0.0]
  ランダムバッチ方式のレンズを用いた連続時間モデルにおけるドロップアウト正規化について検討する。 我々は、長さ$h$の時間間隔でニューロンのバッチをサンプリングすることによって、ドロップアウトを模倣する、偏りのない、よく考えられた推定器を構築した。 次に、単層ニューラルネットワークを専門とし、分類とフローマッチングの理論を検証する。
  論文  参考訳（メタデータ） (2025-10-15T04:19:01Z)
• Assessing One-Dimensional Cluster Stability by Extreme-Point Trimming [0.0]
  本研究では, 一次元試料のテール挙動と幾何学的安定性を評価するための確率的手法を開発した。 有限サンプル補正を含む解析式は、一様仮説とガウス仮説の両方の下で期待される縮退について導出する。 我々はさらにクラスタリングパイプライン(DBSCANなど)に統合し、密度推定やパラメータチューニングなしに1次元のクラスタを検証する能力を示す。
  論文  参考訳（メタデータ） (2025-08-29T21:52:15Z)
• Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget [55.938644481736446]
  本稿では,誤差確率の指数的減衰を保証し,最適な腕識別のための新しいアルゴリズムを提案する。 我々は,複雑性のレベルが異なる様々な問題インスタンスに対する包括的経験的評価を通じて,アルゴリズムの有効性を検証する。
  論文  参考訳（メタデータ） (2025-06-03T02:56:26Z)
• Theory on Score-Mismatched Diffusion Models and Zero-Shot Conditional Samplers [49.97755400231656]
  一般のスコアミスマッチ拡散サンプリング器に対する明示的な次元依存性を持つ最初の性能保証を示す。 その結果, スコアミスマッチは, 目標分布とサンプリング分布の分布バイアスとなり, 目標分布とトレーニング分布の累積ミスマッチに比例することがわかった。 この結果は、測定ノイズに関係なく、任意の条件モデルに対するゼロショット条件付きサンプリングに直接適用することができる。
  論文  参考訳（メタデータ） (2024-10-17T16:42:12Z)
• Universal generalization guarantees for Wasserstein distributionally robust models [10.036727981085223]
  分散ロバストな最適化は、堅牢な機械学習モデルをトレーニングする魅力的な方法として登場した。 最近の統計分析により、ワッサーシュタイン距離に基づくロバストモデルの一般化保証が、次元の呪いに苦しむことのない一般化保証を持つことが証明された。 我々は、任意の輸送コストとパラメトリック損失関数を伴って、幅広いケースをカバーする正確な一般化保証を確立する。
  論文  参考訳（メタデータ） (2024-02-19T09:27:47Z)
• Convergence for score-based generative modeling with polynomial complexity [9.953088581242845]
  我々は、Scoreベースの生成モデルの背後にあるコアメカニックに対する最初の収束保証を証明した。 以前の作品と比較すると、時間的に指数関数的に増加するエラーや、次元の呪いに苦しむエラーは発生しない。 予測器・相関器はどちらの部分のみを使用するよりも収束性が高いことを示す。
  論文  参考訳（メタデータ） (2022-06-13T14:57:35Z)
• Sharper Rates and Flexible Framework for Nonconvex SGD with Client and Data Sampling [64.31011847952006]
  我々は、平均$n$スムーズでおそらくは非カラー関数のほぼ定常点を求める問題を再考する。 我々は$smallsfcolorgreen$を一般化し、事実上あらゆるサンプリングメカニズムで確実に動作するようにします。 我々は、スムーズな非カラー状態における最適境界の最も一般的な、最も正確な解析を提供する。
  論文  参考訳（メタデータ） (2022-06-05T21:32:33Z)
• Nystr\"om Kernel Mean Embeddings [92.10208929236826]
  Nystr"om法に基づく効率的な近似手法を提案する。 サブサンプルサイズの条件は標準の$n-1/2$レートを得るのに十分である。 本稿では,この結果の最大誤差と二次規則の近似への応用について論じる。
  論文  参考訳（メタデータ） (2022-01-31T08:26:06Z)
• Spatially relaxed inference on high-dimensional linear models [48.989769153211995]
  本研究では,空間的に制約されたクラスタリング,統計的推論,アンサンブルを組み合わせ,複数のクラスタリング推論解を集約するアンサンブルクラスタリング推論アルゴリズムの特性について検討する。 アンサンブルクラスタ推論アルゴリズムは,最大クラスター径に等しい$delta$-FWERの標準仮定で$delta$-FWERを制御することを示す。
  論文  参考訳（メタデータ） (2021-06-04T16:37:19Z)
• Computationally efficient sparse clustering [67.95910835079825]
  我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。 ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
  論文  参考訳（メタデータ） (2020-05-21T17:51:30Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。