A Guide to Probability Sampling in High-Dimensional Models

Probability sampling is a collection of methods for selecting data points from a larger population based on a defined probability, rather than by convenience or arbitrary choice. In machine learning and statistics, this approach is critical for building representative samples, reducing bias, and generating reliable model estimates. Techniques range from foundational methods like stratified and cluster sampling to advanced computational strategies like Hashing-Based Estimators (HBE), all designed to improve accuracy, especially in complex, high-dimensional settings.

The Importance of Probability Sampling in High-Dimensional Models

In high-dimensional probability models, the accurate estimation of kernel quantities is often hampered by the quadratic cost of exact evaluation. Traditional random sampling methods frequently prove inefficient because they waste computational effort on low-weight points, failing to adequately capture the "high-weight" regions that drive critical estimates like variance. This can lead to overconfident or under-dispersed posteriors, especially in sequential decision-making processes like Bayesian optimization.

Challenges with Naive Random Sampling

Naive uniform subsampling often misses the most influential data points, leading to unreliable uncertainty estimates. For instance, when estimating a weighted kernel density, if most of the contribution comes from a few points, random sampling is unlikely to select these crucial points, resulting in poor accuracy. The worst-case sample complexity of random sampling depends inversely on the density mass, meaning many samples are needed when the expected density scale is small relative to dominating contributions. This failure to create a representative sample introduces significant error.

Understanding Sampling Bias

The issue described above is a form of sampling bias, a systematic error that occurs when the sample collected is not representative of the underlying population or data distribution. Naive sampling in high-dimensional spaces is particularly prone to this because it treats all points as equally likely to be selected, ignoring the reality that a small subset of points may hold a disproportionate amount of information. This leads to models that are confidently wrong, as they build their understanding on an incomplete and skewed view of the data. Probability sampling techniques are designed specifically to mitigate this bias.

Key Probability Sampling Techniques

To address the limitations of naive random sampling and reduce bias, several probability sampling techniques have been developed. While some originate in classical statistics, their principles are adapted for modern computational challenges.

Stratified Sampling

In traditional statistics, stratified sampling involves dividing a population into distinct subgroups, or "strata," and then drawing a random sample from each stratum. This ensures that all subgroups are represented in the final sample.

In a high-dimensional machine learning context, this principle is adapted to ensure that regions of the data space with different characteristics are all represented. For example, Hashing-Based Estimators (HBE) can implement a form of stratified sampling by treating "high-weight" regions that drive variance as the strata. By sampling points with probability proportional to their contribution to a kernel density estimate, this method focuses computational effort on the most informative "strata," reducing the estimator's variance and avoiding the overconfident uncertainty estimates that arise from missing these key regions.

Cluster Sampling

Cluster sampling involves dividing a population into groups, or "clusters," and then randomly selecting entire clusters to be part of the sample. This is often used when the population is naturally grouped.

However, in high-dimensional data, the notion of a geometric "cluster" or a "nearby" point becomes meaningless. As the number of dimensions (p) increases, all points tend to become equidistant from one another—a phenomenon known as the curse of dimensionality. This makes local averaging methods that rely on proximity, like k-nearest neighbors, highly ineffective.

Advanced methods address this by creating conceptual, rather than geometric, clusters. Hashing-based approaches can identify and sample from regions of high contribution, which act as conceptual clusters of importance. This form of importance sampling allows the model to focus on relevant parts of the data space, even when traditional distance-based clustering fails.

Systematic Sampling

Systematic sampling involves selecting data points from an ordered population at a regular interval, known as the sampling interval. For example, selecting every 10th item from a list.

This concept can be applied in computational models by first creating an ordered structure. For instance, a practical version of HBE hashes a dataset into a series of buckets. A systematic sampling process can then be applied by sampling over and within these buckets in a structured manner. An interpolation parameter (γ) can tune this process: a γ of 1 approximates uniform sampling over data points, while a γ of 0 approximates uniform sampling over the hash buckets themselves. This ensures that buckets with non-trivial contributions are included, providing a more structured and comprehensive sample than purely random selection.

Advanced Implementations

The principles above are often realized through sophisticated computational techniques designed for scalability and efficiency in machine learning.

Hashing-Based Estimators (HBE)

Hashing-Based Estimators approximate kernel quantities by sampling data points according to their contribution and then aggregating them via a sketch. This method is particularly effective because it prioritizes sampling points with higher contributions, thereby shrinking the estimator's variance.

• Mechanism: HBE uses a hash table to quickly identify and sample high-weight points more frequently. For radially decreasing kernels, the required sampling distribution can be achieved through locality-sensitive hashing (LSH)-like mechanisms, which map points so that "near" points collide more often.
• Benefits: HBE prevents false confidence by ensuring that the sampling process is likely to include high-contribution points, which are crucial for accurate variance estimates. It improves upon random sampling by focusing effort where it matters most, especially when kernel values vary wildly across data points.
• Practical Considerations: While theoretically powerful, a literal hashing of the entire dataset for each sampling step can be memory and compute-intensive. Practical implementations often use a hashing-based sketch to manage this, hashing the dataset once into buckets and then performing non-uniform sampling.

Random Fourier Features (RFF)

Random Fourier Features provide a way to replace computationally expensive kernel evaluations with an explicit finite-dimensional feature map. This transforms the problem of computing Gram matrix entries into computing inner products of explicit vectors, which is a foundational step for scalable architectures.

• Underlying Principle: For shift-invariant kernels, Bochner's theorem states that the kernel has a Fourier representation with a non-negative spectral density. RFF approximate this integral by Monte Carlo sampling frequencies (ω) from the spectral density, yielding an unbiased estimate of the kernel value.
• Feature Mapping: RFF define an explicit feature map where k(x,y) is approximately a dot product of feature vectors ϕ(x) and ϕ(y). For D features, ω_j are sampled from the spectral density p, and b_j are sampled uniformly from (0, 2π). The feature map component is ϕ_j(x) = √(2/D) cos(ω_jᵀ x + b_j).

Determining Appropriate Sample Size

A crucial aspect of sampling is determining the sample size (n). In high-dimensional spaces, this becomes particularly challenging. The volume of a high-dimensional space is vast, and the volume of any local neighborhood (like a p-dimensional ball) collapses rapidly as dimensions (p) increase. Consequently, an astronomically large number of samples may be required to adequately cover the space.

The required sample size is also influenced by the data distribution itself. The sample complexity often depends inversely on the density mass of the regions of interest. If the most important contributions come from a few dense points, a smaller, well-targeted sample might suffice. Conversely, if the contributions are sparse and spread out, a much larger sample is needed. Techniques like HBE that focus on high-contribution points are therefore more sample-efficient than naive random sampling.

Probability vs. Non-Probability Sampling

The choice between probability and non-probability sampling methods significantly impacts the reliability and generalizability of results. Probability sampling provides a framework for controlling and measuring error, which is essential for robust modeling.

Hardening Workflow for Reliability

To ensure the reliability of models using probability sampling, especially in sequential Bayesian optimization, a practical hardening workflow is recommended:

1. Choose m large enough: Ensure that the number of random features or inducing points (m) is sufficient to represent posterior correlations.
2. Initialize Z strategically: Initialize inducing points (Z) with a strategy that captures input diversity, rather than just random training points.
3. Validate predictive calibration: Before trusting acquisition-driven exploration, validate predictive calibration using a scoring rule like CRPS/LOO-CRPS.

Frequently Asked Questions

Conclusion

Probability sampling methods are indispensable for building reliable and scalable high-dimensional models. By moving beyond naive random selection, techniques like stratified, cluster, and systematic sampling provide a structured framework for reducing bias and ensuring a representative sample. In modern machine learning, these principles are implemented through advanced methods like Hashing-Based Estimators and Random Fourier Features, which directly address the curse of dimensionality and the limitations of uniform subsampling. By strategically focusing on high-contribution data points and understanding the factors that drive sample size, practitioners can mitigate issues like overconfidence and build more accurate and trustworthy models.

Sources & References

• [1706.09233] 1 Introduction
• [1905.09501] Bayesian Item Response Modeling in R with brms and Stan
• [2106.01963] A Survey on Optimal Transport for Machine Learning: Theory and Applications
• [2505.06589] Optimal Transport for Machine Learners
• Fast Kernel Summation in High Dimensions via Slicing and Fourier Transforms
• A Survey on Diffusion Models for Time Series and Spatio-Temporal Data
• A Survey on Algorithmic Developments in Optimal Transport Problem with Applications
• Optimal Transport for Machine Learners Course notes
• A Systematic Review of Spatio-Temporal Statistical Models: Theory, Structure, and Applications
• Optimal and Diffusion Transports in Machine Learning