CS Paper Radar

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

Luc Pronzato, Anatoly Zhigljavsky

cs.LG stat.ML ·submitted 2026-11-18 14:31 UTC · v1
theoryunusual

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.

Comment
25 pages, 16 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Simultaneous Near-Optimal Region Identification in Continuous Simulation Optimization: Minimax Complexity and Adaptive Sampling

cs.LG stat.ML ·2026-11-10 ·Yilin Zheng, Haowei Wang, Wenjia Wang, Szu Hui Ng
theory similarity 0.55
Abstract

Simulation optimization typically returns a single estimated optimal point. When decisions also depend on criteria evaluated independently of simulation, such as resource cost, the decision maker instead needs the set of designs whose expected performance lies within a tolerance of the optimum, often choosing the tolerance only after seeing the tradeoffs. We study how to identify these near-optimal regions on a continuous design space, simultaneously for all tolerances up to a prescribed maximum $T$, with region estimation error at most $η$. We show that region identification is not a by-product of optimization. Specifically, when $α>ν$, any procedure, even one given the optimal design in advance, needs at least $Ω\bigl(η^{-(2+d/ν)}\min\{1,KT^{d/α}\}\bigr)$ simulation evaluations, where $d$ is the dimension, $ν$ the smoothness, and $(K,α)$ the covering parameters that describe the geometry of the near-optimal designs. We propose SASORI, which returns an estimated optimal point and the regions for all tolerances from the same evaluations, matching this lower bound up to logarithmic factors. SASORI also achieves the optimal tradeoff between region estimation error and cumulative regret, and reduces to a minimax-optimal simulation optimization procedure at zero tolerance. Numerical experiments illustrate the effectiveness of our proposed method.

0.20

Optimal random quantisers for spherically symmetric distributions

cs.LG math.STstat.ML ·2026-10-08 ·Luc Pronzato, Anatoly Zhigljavsky
theory similarity 0.55
Abstract

Zador's celebrated theorem is a cornerstone of optimal quantisation: it establishes both the weak limit of the empirical distribution of an optimal $n$-point quantiser in $R^d$ and the decay rate of the associated $L_s$-mean quantisation error. In large dimension, however, observing this asymptotic behaviour requires an astronomically large sample size. We prove that, for spherically symmetric target distributions, optimisation over all spherically symmetric distributions is a convex problem and derive an equivalence theorem that both characterises global optimality and yields a constructive algorithm. We show that, for moderate $n$, random quantisers uniformly distributed on a sphere of suitably chosen radius $R$ perform exceptionally well and, over a broad range of values of $n$, are numerically certified to be optimal among all random quantisers. Their expected distortion has an explicit integral representation that can be evaluated to arbitrary precision, and we prove concentration across random quantisers: the distortion variance tends to zero as $n\to\infty$ for fixed $d$. For $s=2$, both the optimal radius and the associated minimum expected distortion admit exact expressions. For general $s$, the optimal radius can be determined efficiently, and extreme-value theory provides useful approximations when $n$ grows with $d$. Depending on this growth rate, $R$ either converges to zero or approaches a positive limit that is independent of $s$.

0.57

Improved Multilayered PCPs and Hypergraph Vertex Cover

cs.CC cs.DS ·2026-09-06 ·Karthik C. S., Dor Minzer
similarity 0.55
Abstract

We present two elementary constructions of multilayered PCPs that improve upon prior constructions in two ways. Specifically, we give one construction of quasi-linear size, and another one with $2$-to-$2$ constraints. Using these constructions we obtain the following results for the hypergraph vertex cover problem: $\bullet$ For $k=3$, for all $\varepsilon>0$, approximating the minimum vertex cover of a given $3$-uniform hypergraph within factor $1+\sqrt{2}-\varepsilon$ is NP-hard. Previously, the best known result due to [Dinur, Guruswami, Khot, Regev, SICOMP 2005] achieved a factor of $2-\varepsilon$. $\bullet$ For $k\geq 4$, for all $\varepsilon>0$, approximating the minimum vertex cover of a given $k$-uniform hypergraph within factor $k-\varepsilon$ is NP-hard, which is tight. Previous works established this result assuming the Unique-Games Conjecture [Khot, Regev, JCSS 2008], and a weaker factor of $k-1-\varepsilon$ for standard NP-hardness [Dinur, Guruswami, Khot, Regev, SICOMP 2005]. $\bullet$ Assuming the Exponential Time Hypothesis, for all $k\geq 3$ and $\varepsilon>0$ there is $C>0$ such that no $2^{n/\log^C n}$-time algorithm approximates the minimum vertex cover in a $k$-uniform, $n$-vertex hypergraph within factor $k-1-\varepsilon$. The proofs were obtained using ChatGPT 5.6 Pro and subsequently rewritten by the communicators.

0.24

Efficient lifts into odd dimensions of Spherical $5$- and $7$-designs with Balanced Halves

cs.IT math.CO ·2026-10-08 ·Konstantin Delchev, Boryan Yordanov
similarity 0.55
Abstract · 13 pages, 3 tables

We propose constructions of spherical $5$- and $7$-designs in odd dimensions by lifting balanced halves of even-dimensional designs to several layers of suitable latitudes. For every odd dimension, we obtain an explicit spherical $5$-design with at most $60(d^2-1)$ points, attaining the optimal quadratic order in the dimension. Assuming Zauner's conjecture, this bound improves to $7.5(d-1)^2$. For every odd $d \geq 9$, we also construct a spherical $7$-design with $110M$ points from a complex projective $3$-design with $M$ points in $\mathbb{CP}^{(d-3)/2}$.

0.21

Approximating the Euclidean Ball by Polytopes: Surprising Rates in High Dimensions

cs.CG math.MGcs.LGmath.PR ·2026-10-26 ·Yegor Gorodzha, Steven Hoehner, Gil Kur
theory similarity 0.54
Abstract · 71 pages, 1 figure, 1 table. v2: exposition and references revised for a broader audience

We provide sharp estimates on the number of vertices needed to approximate the Euclidean unit ball $B_d\subset\mathbb R^d$ with relative symmetric-difference volume error at most $\varepsilon\in(0,1)$. We show that the minimum vertex budget $N_\varepsilon(d)$ satisfies $$\log N_\varepsilon(d)\asymp d\log\left(1+\frac1{\varepsilon\sqrt d}\right).$$ In particular, $\exp(O(\sqrt d/\varepsilon))$ vertices suffice for every $\varepsilon\in(0,1)$ and all sufficiently large $d$. We also prove that achieving a fixed error $\varepsilon\in(0,1)$ requires at least $Ω\bigl((\tfrac{1+\varepsilon}{2\sqrt\varepsilon})^{d-1}\bigr)$ facets, an exponential number in $d$. We extend our vertex approximation result to Gaussian symmetric-difference error, and give a positive answer to the question of De, Nadimpalli, and Servedio about subexponential vertex complexity for approximating Euclidean balls. We also disprove a Macbeath-type extremality principle for unrestricted vertex approximation. Whereas the ball uniformly maximizes the inscribed approximation error among all convex bodies (Macbeath, 1951), we show that approximating the hypercube $[-1,1]^d$ to relative error $\varepsilon$, with $δ:=1-\varepsilon$, requires $N\ge\fracδ{2}\exp(Ω(δ^2d/\log^2(2/δ)))$ vertices whenever $d\ge16\log(2/δ)$. Thus, when $d$ is large, the cube is harder to approximate than the ball in this sense. Finally, we determine the sharp dimensional order of the classical Laguerre-Delone triangulation number, showing that $\mathrm{ldel}_{d-1}=Θ(d^{-1/2})$ as $d\to\infty$. This improves both the upper bound of Ludwig, Schütt, and Werner and the lower bound of Böröczky by a factor of order $\sqrt d$. By classical asymptotic approximation theorems (Ludwig, 1999), this improvement applies to every convex body in $\mathbb R^d$ with $C^2$ boundary and positive Gaussian curvature.

0.34

Algebraic-Geometric Parvaresh--Vardy Subspace Designs and Rank Condensers

cs.CC cs.IT ·2026-09-26 ·Gil Cohen, Dean Doron, Noam Goldgraber
published similarity 0.54
Abstract

A subspace design is a collection of subspaces $H_1,\ldots,H_n$ of $\mathbb{F}_q^k$ with the property that no low-dimensional subspace $W$ intersects the collection "too much". Subspace designs and related objects in linear-algebraic pseudorandomness have found a broad range of applications, ranging from list decoding to derandomizing algorithms. We construct explicit strong subspace designs over every finite field. In the extremal case where the co-dimension $t$ of each $H_i$ is equal to the dimension of $W$, for every constant field size our construction attains $n=Ω(k)$ and matches the probabilistic intersection bound up to a constant factor. All previous constructions required the field size to grow with $t$ (or $k$). Our subspace designs also imply new constructions of rank condensers over arbitrary finite fields. This result is the first to achieve an optimal dependence on $k$ while maintaining both a constant output entropy rate and a constant field size. As an application, we construct lossless rank extractors for linear sources of rank $r$, for all $r < q$, with parameters matching those of Guo, Raj, Shangguan and Zhang (FOCS '26), thereby generalizing their result to prime fields and smaller field sizes. Our construction is based on an algebraic-geometric version of the Parvaresh--Vardy codes (Parvaresh--Vardy FOCS '05, Guruswami ECCC '05), extending the framework underlying the condensers of Guruswami, Umans and Vadhan (JACM '09). We view our construction as a linear-algebraic analysis -- tailored to affine sources -- of the GUV construction, generalized to functions over algebraic curves. More specifically, inspired by Ta-Shma and Umans (CCC '12) we develop a two-level evaluation scheme, where we first evaluate a function on a curve at extension-field points, and then evaluate a corresponding affine-linear polynomial to obtain outputs over the base field.

0.59

Optimal Coresets for Hyperbolic Farthest-Point Queries via Ideal-Boundary Envelopes

cs.CG ·2026-10-01 ·Eunku Park
theory similarity 0.54
Abstract

We study coresets for farthest-point queries in hyperbolic space. Given a nonempty finite set $P \subset \mathbb{H}^D$ and $0<\varepsilon \le 1$, we seek a coreset $P_{\varepsilon} \subseteq P$ whose farthest distance from every query point underestimates that of $P$ by at most an additive $\varepsilon$ and retains at least a $1-\varepsilon$ fraction of it. For every fixed $D \ge 2$, we prove that the optimal worst-case coreset size is $Θ\bigl(\varepsilon^{-(D-1)/2}\bigr)$. Our main geometric ingredient is an exact reduction from hyperbolic queries to an upper envelope on the ideal boundary. In the hyperboloid model, each input point induces a positive boundary-score function whose logarithm gives its asymptotic distance offset along geodesic rays. We define the \emph{ideal-boundary envelope} as the pointwise maximum of these functions and prove that the supremum additive loss over all queries equals the maximum logarithmic gap between the input and coreset envelopes. For the upper bound, we move the minimum-enclosing-ball center to the origin and normalize the spatial coordinates, obtaining a bounded Euclidean point set whose boundary envelope is bounded away from zero. A standard Euclidean kernel then approximates all directional score maxima simultaneously, and the structure theorem yields both guarantees. For the lower bound, a spherical packing on a fixed-radius hyperbolic sphere, together with antipodal queries and the hyperbolic cosine law, makes every input point indispensable, matching the upper bound even for either guarantee separately.

0.36

Restricted Eigenvalues Beyond Gaussian Width: Threshold Occupancy under Heavy Tails

cs.LG ·2026-09-03 ·Shi Fu, Huibo Xu, Qixin Zhang, Dacheng Tao
benchmark similarity 0.53
Abstract

Restricted eigenvalue (RE) bounds govern stable recovery by norm-regularized estimators. For isotropic sub-Gaussian measurements, the benchmark sample size is $1+w(A)^2$, where $w(A)$ is the Gaussian width of the normalized descent cone. The COLT 2015 open-problem note (Banerjee et al., 2015) asked whether the same law follows for heavy-tailed designs from a uniform small-ball condition alone. We give an explicit and systematic negative answer to the general question as formulated there: the proposed law fails in its full dimension-free, arbitrary-set form, and the missing obstruction is simultaneous threshold occupancy. A constant-width polyhedral descent cone with fixed small-ball constants has zero empirical RE on every sample path up to half the ambient dimension. More generally, every finite range space admits exact threshold encoding in an arbitrarily narrow spherical cap and a lift to a full polyhedral descent-cone section. For every fixed threshold VC dimension $d$, as $β\downarrow0$, the sharp worst-case sample complexity is $Θ(β^{-1}[d\log(1/β)+\log(1/δ)])$. The separation persists under exact isotropy and all finite moments: on the same constant-width cone, Gaussian measurements succeed with $O(1+\log(1/δ))$ samples, whereas an isotropic heavy-tailed design fails pathwise for $n\lesssim\sqrt{p/\log p}$. Gaussian smoothing yields an everywhere-positive $C^\infty$ density while retaining arbitrarily poor RE. Under isotropy, a distribution-free fallback governed by affine dimension times squared enclosing radius is sharp on this family.

0.27