# A Variance-Based Analysis of Sample Complexity for Grid Coverage

arXiv: https://arxiv.org/abs/2511.17784 · HTML: https://mlsanity.com/paper/2511.17784/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 22 references that are in the map.
- First posted on arXiv 21 Nov 2025.

## Builds on (most cited first, 5 of 5)

- [Continuous control with deep reinforcement learning](https://mlsanity.com/paper/1509.02971/) (2015)
- [Policy Gradient and Actor-Critic Learning in Continuous Time and Space: Theory and Algorithms](https://mlsanity.com/paper/2111.11232/) (2021)
- [A Statistical Approach to Assessing Neural Network Robustness](https://mlsanity.com/paper/1811.07209/) (2018)
- [Deep Learning for Computing Convergence Rates of Markov Chains](https://mlsanity.com/paper/2405.20435/) (2024)
- [Consistency and Finite Sample Behavior of Binary Class Probability Estimation](https://mlsanity.com/paper/1908.11823/) (2019)

## Abstract (arXiv)

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( tildeCln(frac2tildeCδ)), 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 δ → 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.