stat.MLNov 18, 2026

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

Authors: Luc Pronzato, Anatoly Zhigljavsky

Organizations: Laboratoire I3S, CNRS-Université Côte d’Azur, Sophia Antipolis, France · School of Mathematics, Cardiff University, UK

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 dd 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 2d2^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 UU 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 nn with small LsL_s-mean quantization error. The support of the resulting distribution is then used to construct designs, possibly incrementally, with sizes up to nn. We demonstrate that, for moderate nn, 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.

Figures & tables

Explore similar work

CardsList
  1. Optimal random quantisers for spherically symmetric distributions

    Oct 8, 2026Luc Pronzato, Anatoly ZhigljavskyVector QuantizationRate-Distortion Optimization

  2. Finding Low Star Discrepancy 3D Kronecker Point Sets Using Algorithm Configuration Techniques

    Apr 1, 2026Imène Ait Abderrahim, Carola Doerr, Martin Durand

  3. Derandomizing Dense Binary Hypervector Codebooks for Quantized Scalars

    Sep 29, 2026Dmitri Rachkovskij, Evgeny Osipov, Olexander Volkov +2Vector QuantizationHyperdimensional Computing