提出更优采样复杂度分析方法，显著降低高置信度下的采样需求。
A Variance-Based Analysis of Sample Complexity for Grid Coverage
- 基于方差分析与集中不等式，推导出对失败概率对数依赖的采样边界
- 在小失败概率下，采样数仅需约 $\tilde{C}\ln(2\tilde{C}/δ)$，远低于传统线性 $1/δ$
- 适用于高维网格覆盖验证，尤其适合高置信度场景的高效采样设计
通过随机采样验证连续空间中的均匀性条件是机器学习与控制理论的基础问题，但经典覆盖率分析常给出保守估计，尤其在低失败概率时。本文研究 $d$-维单位超立方体上的均匀随机采样，分析离散化后未被覆盖的子立方体数量。通过将集中不等式应用于未覆盖计数统计量，得到样本复杂度界为 $M = O(\tilde{C} \ln(2\tilde{C}/δ))$，相较于经典的 $1/δ$ 线性依赖显著改进。在标准 Lipschitz 与均匀性假设下，提供自包含推导，并与经典优惠券收集速率对比。数值实验涵盖多维度、精度水平与置信目标，表明该界更紧密贴合实际覆盖需求，且随 $δ \to 0$ 表现良好。研究成果为依赖网格覆盖率保证的算法提供了更精确的理论工具，可实现更高效的采样，尤其在高置信度情形。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。