Sparse designs via quantization of the uniform measure on high-dimensional hypercubes

Luc Pronzato, Anatoly ZhigljavskyarXiv 2026 · arXiv

In the world of computer experiments and high-dimensional modeling, "space-filling designs" are the gold standard. The goal is simple: pick a set of points that covers your experimental domain as evenly as possible. Traditionally, researchers have used "maximin" (maximizing the minimum distance between points) or "minimax" (minimizing the maximum distance from any point to the design) criteria.

However, as dimensions grow, these traditional methods hit a wall. A new paper by Luc Pronzato and Anatoly Zhigljavsky, titled "Sparse designs via quantization of the uniform measure on high-dimensional hypercubes," suggests we’ve been looking at the problem through the wrong lens.

TL;DR

This paper proposes using quantization error instead of traditional distance-based metrics to create space-filling designs in high dimensions. The authors discover a surprising "aha!" moment: for moderate sample sizes, the most efficient way to cover a high-dimensional hypercube is to place points on the vertices of a smaller inner hypercube, rather than spreading them across the entire space.

What Problem Does This Paper Address?

In high dimensions ($d > 10$), the "curse of dimensionality" makes space-filling incredibly difficult. Traditional maximin and minimax designs suffer from two major flaws:

  1. Volume Concentration: In high dimensions, almost all the volume of a hypercube is concentrated near its boundaries and corners. Maximin/minimax criteria are hyper-sensitive to these boundaries, often pushing points into "useless" corners.
  2. Point Requirements: To truly "fill" a 20-dimensional space using traditional methods, you would need an astronomical number of points—far more than any practical computer experiment can afford.

The authors argue that we need a "global" measure of space-fillingness that accounts for the entire distribution of distances, not just the extreme outliers.

Methods

The authors pivot to quantization error ($L_s$-mean). This metric measures the average distance from a random point in the hypercube to its nearest design point.

To make this mathematically tractable in high dimensions, they employ several clever techniques:

  • Spherically Symmetric Approximation: Working with a hypercube is hard. The authors approximate the uniform measure of a hypercube with a spherically symmetric distribution. They use moment-matching to ensure this "substitute" distribution has the same first three moments of the squared norm ($\|X\|^2$) as the actual hypercube.
  • Optimal Random Quantizers: Building on Zador’s theorem, they find the optimal probability distribution from which to sample design points.
  • Inner Hypercube Scaling: They identify an optimal scaling factor $\delta^*$. For small sample sizes, the best designs are supported on the vertices of a hypercube scaled by $\delta^* < 1$.
  • Greedy Packing on Fractional Factorials: To turn these probability distributions into actual point sets, they use two-level fractional factorial designs as candidate sets and refine them using a greedy packing algorithm.
Figure 1: Left: a∗(- - -), b∗(· · · ) and M∗(—) as functions of d for α = 1, δ = 1 (▼) and α = 0.1, δ = 0.6 (•). Right: ϕα,δ(·) for d = 20 and α = 1, δ = 1 (i.e., Pα,δ = P1,1 = µ, ▼—▼) and α = 0.1, δ = 0.6 (•—•); the right limit √M∗of the support is indicated.

Datasets

The paper is methodological and uses synthetic benchmarks rather than real-world datasets. The authors evaluate their approach in dimensions $d=10, 20, 30, \text{ and } 50$. They compare their designs against:

  • Sobol' sequences (a standard quasi-Monte Carlo method).
  • Scrambled Sobol' sequences.
  • Uniform random designs.
  • Greedy packing with boundary avoidance.

Key Insights and Ideas

  • The Concentration of Norms: Thanks to the Central Limit Theorem, the distance of a random point from the center of a high-dimensional hypercube concentrates around a specific value ($\sqrt{d/3}$). This is why a spherical shell approximation works so well.
  • Pessimism is Productive: The spherical approximation is "pessimistic" because it ignores the hypercube's corners. Paradoxically, this makes the resulting designs better because they don't waste points trying to cover those low-volume corner regions.
  • The Vertex Advantage: For "sparse" designs (where the number of points $n$ is much smaller than $2^d$), placing points on the vertices of a small inner hypercube is significantly more efficient than spreading them uniformly.
Figure 2: The density of the squared norm $\|X\|^2$ for a hypercube (red stars) is remarkably well-approximated by the authors' beta-distribution model (orange diamonds), especially as dimension $d$ increases.

Key Results

  • Superior Performance: In a 30-dimensional test, the authors' vertex-based designs achieved lower quantization error than scrambled Sobol' sequences, which are widely considered the industry standard.
  • Optimal Scaling: The authors provide an explicit "extreme-value approximation" (Eq. 19) to calculate exactly how much to shrink the inner hypercube based on the dimension $d$ and the desired number of points $n$.
  • Efficiency: Using a fractional factorial subset of vertices combined with a greedy algorithm provides a "best of both worlds" approach: it’s computationally efficient and yields highly regular, well-spaced designs.

Limitations and Future Work

  • The Projection Trade-off: Designs concentrated on vertices have poor "projections." If you only look at a 2D slice of a 30D vertex design, many points will overlap, leaving large gaps. The authors suggest a perturbation method to "blur" the vertices, but this inherently increases the quantization error in the full space.
  • Target Size Dependency: The current method requires the user to specify the maximum design size $n$ upfront to optimize the distribution. Future work could look into "any-time" designs that remain optimal as points are added one by one.
  • Non-Uniform Measures: While this paper focuses on the uniform measure (the most common case), the framework could potentially be extended to non-uniform measures (e.g., Gaussian) common in uncertainty quantification.

For those interested in implementation, the authors have made their MATLAB scripts available on GitHub.

Summary updated

Abstract

While the notions of sphere packing and sphere covering underlie the most widely used criteria for space-filling design in computer experiments, namely, the maximin and minimax approaches, they suffer from major drawbacks in high dimensions. First, when the dimension $d$ is very large, deploying a space-filling design requires an extremely large number of design points, making the very notion of a space-filling design questionable. Second, these two design characteristics are highly sensitive to boundaries, particularly when the design domain is a hypercube (the case considered in this paper), and especially to its vertices. This sensitivity is particularly acute when the design size is less than $2^d$. Instead of considering the maximin or minimax criterion, we consider here the quantization error of the uniform measure on the hypercube. This error has three key advantages: it accounts for the entire distribution of distances from a random point $U$ to the design, is less sensitive to boundary effects than the maximin and minimax criteria, and, thanks to Zador's celebrated theorem, enables a smooth and natural transition to uniform designs as the design size tends to infinity. Building on recent results on the construction of optimal random quantizers for spherically symmetric distributions (arXiv:2610.11772) we propose a method to generate random designs of a given target size $n$ with small $L_s$-mean quantization error. The support of the resulting distribution is then used to construct designs, possibly incrementally, with sizes up to $n$. We demonstrate that, for moderate $n$, designs supported on a fractional factorial subset of the vertices of a small hypercube perform exceptionally well---and significantly better than designs uniformly distributed over the entire hypercube. We also explain how to account for projections onto lower-dimensional subspaces.
BibTeX
@misc{pronzato2026sparse,
  author = {Luc Pronzato and Anatoly Zhigljavsky},
  title = {{Sparse designs via quantization of the uniform measure on high-dimensional hypercubes}},
  year = {2026},
  eprint = {2611.24507},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.24507},
}
Figure