Subgroup Rank-1 Lattice for Practical High-dimensional Black-box Integral Approximation

Yueming Lyu

cs.LGSep 28, 2026

Subgroup Rank-1 Lattice for Practical High-dimensional Black-box Integral Approximation

Authors: Yueming Lyu

Organizations: Centre for Frontier AI Research (CFAR) Agency for Science, Technology and Research (A*STAR) 1 Fusionopolis Way #16-16 Connexis Singapore, 138632

Abstract

Estimating integrals of black-box, high-dimensional functions, from expectations and kernel mean embeddings to the softmax kernel in self-attention, is a basic subroutine in machine learning. Rank-1 lattice rules suit this setting: they query the integrand only at a fixed point set and need no gradients. When the $n$ points serve as a design matrix $X\in\mathbb{R}^{n\times d}$ for a feature map, however, computing $Ψ(X)^\top v$ or $Ψ(X)w$ for an elementwise nonlinearity $Ψ$ costs $O(nd)$ time and memory for any standard quasi-Monte Carlo point set. We study subgroup rank-1 lattices, whose Korobov generator $(1,t,\dots,t^{d-1})$ uses a scalar $t$ of fixed multiplicative order $m$ . Splitting $\mathbb{F}_n^\times$ into cosets of $\langle t\rangle$ reduces both maps to short cyclic correlations evaluated by FFT, giving exact results for arbitrary $Ψ$ in $O(n\log m)$ time and $O(n)$ memory, without forming $X$ . Since fixing $m$ falls outside classical component-by-component theory, we prove convergence directly: via resultants with the cyclotomic polynomial $Φ_m$ , the squared worst-case error in the Korobov space decays as $O(n^{-(α-1)/(m-1)})$ for prime $m\ge d+1$ , and this threshold is exact. Using the splitting of $n$ in $\mathbb{Q}(ζ_m)$ , averaging over the $m-1$ admissible generators improves the constant by a factor $Θ(m-1)$ . Empirically, the subgroup lattice beats Gaussian and orthogonal random features and scrambled Sobol' and Halton points in 49 of 54 synthetic kernel-estimation settings and all 45 softmax-attention settings on nine real datasets, and builds a sample set with $d=2048$ , $n\approx4.1\times10^7$ in 2.3 ms.

Figures & tables

Method	Cost	Requires
Direct evaluation, i.e., the standard cost for a Halton or Sobol’ sequence, or a generic rank-1 lattice	$O(nd)$	nothing
Proposition 11 (coset FFTs)	$O(n\log m)$ (i.e. $O(n\log d)$ for $m=\Theta(d)$ )	power-form generator, small order ( $m\ll n$ )

Table 1: Cost of computing

Y=\Psi(X)^{\top}v

for the full

n

-point lattice, for an arbitrary elementwise map

\Psi

$n$	$m$	$d$	$\Psi$	$\max\|\text{err }Y\|$ (Alg. 1 )	$\max\|\text{err }u\|$ (Alg. 2 )
113	7	5	$\mathrm{id}$	$2.0\times 10^{-15}$	$8.9\times 10^{-16}$
113	7	5	$\cos+0.3x^{2}$	$3.6\times 10^{-15}$	$1.8\times 10^{-15}$
1321	11	8	$\mathrm{id}$	$3.6\times 10^{-14}$	$1.8\times 10^{-15}$
1321	11	8	$\cos+0.3x^{2}$	$5.3\times 10^{-14}$	$2.7\times 10^{-15}$
2029	13	9	$\mathrm{id}$	$6.4\times 10^{-14}$	$2.7\times 10^{-15}$
2029	13	9	$\cos+0.3x^{2}$	$4.3\times 10^{-14}$	$1.8\times 10^{-15}$

Table 2: Correctness check: maximum absolute entrywise error between each fast method and direct

O(nm)

evaluation, for both the nonlinear and the trivial

\Psi

. All errors are at floating-point rounding level.

$n$	$q=(n-1)/m$	direct $O(nd)$	coset-FFT $O(n\log m)$
16,007	302	0.0077	0.0014
31,907	602	0.0174	0.0027
57,559	1,086	0.0382	0.0046
132,607	2,502	0.1114	0.0114
337,081	6,360	0.3813	0.0292
717,091	13,530	0.8562	0.0672

Table 3: Wall-clock time (seconds, best of 3 runs) for

Y=\Psi(X)^{\top}v

(

d=50

m=53

\Psi=\mathrm{id}

shown; nonlinear

\Psi

discussed in text), direct

O(nd)

evaluation vs. coset-FFT ( Algorithm 1 ).

Figure 1: empirical decay v.s. predicted upper-bound exponent at $m=5$ (prime) and $\alpha=2$

$n$	shortest simultaneous-bad $h$	$R(h)$	$R(h)/n^{2}$
$41$	$(-7,2,-3)$	$1{,}681$	$1$
$131$	$(-7,2,-13)$	$17{,}161$	$1$
$401$	$(-27,15,-19)$	$160{,}801$	$1$
$1231$	$(43,-32,-84)$	$92{,}437{,}021$	$61$

Table 4: Verification of Lemma 21 at

m=5

d=3

: the shortest

h

simultaneously bad for two non-inverse order-

5

elements, and the resulting resultant.

$d$	$n_{0}/d$	$n$	winning method	subgroup RLerr	winner’s RLerr
8	10,000	80,071	Halton	$1.083\times 10^{-4}$	$9.856\times 10^{-5}$ (within noise)
8	20,000	160,073	Sobol	$7.927\times 10^{-5}$	$3.455\times 10^{-5}$
16	20,000	320,107	Sobol	$3.982\times 10^{-5}$	$2.428\times 10^{-5}$
32	10,000	321,199	Sobol	$8.916\times 10^{-5}$	$2.895\times 10^{-5}$
1024	1,000	1,047,031	Halton	$1.470\times 10^{-5}$	$1.448\times 10^{-5}$ (within noise, $1.5\%$ apart)

Table 5: Synthetic

\exp(\mathbf{x}^{\top}\mathbf{y})

estimation: the five (of

54

) configurations in which the subgroup lattice was not the most accurate method. Four of them are at the smallest tested dimensions and the largest tested

n

; the fifth is an isolated near-tie at

d=1024

$d$	subgroup RLerr @ smallest $n$	advantage	subgroup RLerr @ largest $n$	advantage
8	$2.265\times 10^{-3}$	$3.2\times$ (Sobol)	$7.927\times 10^{-5}$	$0.4\times$ (Sobol wins)
16	$2.329\times 10^{-3}$	$4.7\times$ (Gaussian)	$3.982\times 10^{-5}$	$0.6\times$ (Sobol wins)
32	$6.979\times 10^{-4}$	$8.4\times$ (Halton)	$6.292\times 10^{-6}$	$3.4\times$ (Halton)
64	$3.972\times 10^{-4}$	$4.2\times$ (Halton)	$3.610\times 10^{-6}$	$2.6\times$ (Sobol)
128	$5.628\times 10^{-4}$	$1.8\times$ (ORF)	$2.187\times 10^{-6}$	$2.0\times$ (Halton)
256	$1.969\times 10^{-4}$	$2.0\times$ (Sobol)	$7.746\times 10^{-7}$	$4.9\times$ (Gaussian)

Table 6: Advantage of the subgroup lattice (best-of-{Gaussian, ORF, Sobol, Halton} error

\div

subgroup error;

>1

favors the subgroup lattice) at the smallest and the largest tested

n

for each

d

, with the closest competing baseline named in parentheses.

Figure 2: Subgroup rank-1 lattice vs. Gaussian / ORF / Sobol / Halton: mean relative error of $\exp(\mathbf{x}^{\top}\mathbf{y})$ estimation, one panel per dimension $d\in\{8,\dots,2048\}$ , log-log axes, shaded bands $\pm 1$ standard deviation over repeats.

Figure 3: Wall-clock time to construct the full sample set of $n$ Gaussianized directions, subgroup rank-1 lattice vs. Gaussian / ORF / Sobol’ / Halton, one panel per dimension $d\in\{8,\dots,2048\}$ , log-log axes, shaded bands $\pm 1$ standard deviation over $5$ repeats.

$d$	$n$	Subgroup	Gaussian	ORF	Sobol’	Halton	Gauss. / Subgr.
8	160,073	0.083 ms	0.023 ms	18.9 ms	5.9 ms	53.6 ms	$0.28\times$
16	320,107	0.088 ms	0.049 ms	33.5 ms	20.0 ms	146 ms	$0.56\times$
32	641,057	0.099 ms	0.150 ms	50.9 ms	81.8 ms	466 ms	$1.5\times$
64	1,280,161	0.132 ms	0.549 ms	30.3 s	0.32 s	1.51 s	$4.2\times$
128	2,561,263	0.198 ms	2.18 ms	78.4 s	1.08 s	5.14 s	$11\times$
256	5,130,809	0.362 ms	8.56 ms	220 s	3.43 s	17.7 s	$24\times$

Table 7: Sample set construction time at the largest tested

n

for each

d

(

n_{0}/d=20{,}000

), mean over

5

repeats. The last column is the Gaussian time divided by the subgroup time (

>1

favors the subgroup lattice).

Dataset	Points ( $N$ )	Dimension ( $d$ )
yandex-200-cosine	1,000,000	200
laion-clip-512-normalized	999,448	512
arxiv-nomic-768-normalized	1,344,643	768
landmark-nomic-768-normalized	760,757	768
imagenet-align-640-normalized	315,648	640
llama-128-ip	255,921	128

Table 8: Dataset Summary

Dataset	$d$	subgroup wins	advantage range	mean advantage
celeba-resnet-2048-cosine	2048	5/5	$1.13$ – $1.39\times$	$1.27\times$
arxiv-nomic-768-normalized	768	5/5	$1.57$ – $1.84\times$	$1.70\times$
landmark-nomic-768-normalized	768	5/5	$1.95$ – $3.37\times$	$2.83\times$
coco-nomic-768-normalized	768	5/5	$1.37$ – $1.82\times$	$1.59\times$
imagenet-align-640-normalized	640	5/5	$1.52$ – $1.76\times$	$1.66\times$
laion-clip-512-normalized	512	5/5	$1.25$ – $1.64\times$	$1.38\times$

Table 9: Subgroup lattice’s advantage over the best of {Gaussian, ORF, Sobol, Halton} on softmax-attention approximation, by dataset, across the five tested ratios

n_{0}/d\in\{100,\dots,500\}

Figure 4: Subgroup rank-1 lattice vs. Gaussian / ORF / Sobol / Halton: self-normalized softmax-attention approximation error on all $9$ datasets of Table 8 , one panel per dataset, log-log axes, shaded bands $\pm 1$ standard deviation over repeats.

Explore similar work

Random features for Grassmannian kernel approximation with bounded rank-one projections
Aug 4, 2026Rémi Delogne, Laurent JacquesAtom-Averaged Features Kernel Method
INMA/ICTEAM, UCLouvain, Belgium
Exact Schur-Sylvester Dimensionality Reductions for Non-Smooth Stochastic Complexity and Manifold Sampling
Jun 22, 2026Trenton Lau, Gary P. T. ChoiMaximum Likelihood Optimal Sample Complexity
Department of Mathematics, The Chinese University of Hong Kong
Kolmogorov-Arnold Classifier Systems as Universal Approximators
Sep 29, 2026Hiroki Shiraishi, Hisao Ishibuchi, Masaya NakataKolmogorov-Arnold Networks Classifier
Graduate School of Engineering Science, Yokohama National University, Yokohama 240-8501, Japan · Digital Healthcare Research Department, Hitachi, Ltd., Tokyo 185-8601, Japan · Department of Computer Science and Engineering, Southern University of Science and Technology, Shenzhen 518055, China +1

Aug 4, 2026, cs.LGJ/K move · Enter open · S save

Random features for Grassmannian kernel approximation with bounded rank-one projections

Rémi Delogne, Laurent Jacques

INMA/ICTEAM, UCLouvain, Belgium

Atom-Averaged Features Kernel Method Subspace Approximation Random

Open paper AskPDF arXiv

We propose a family of random feature maps for scalable kernel machines on low-dimensional subspaces, ie on the Grassmannian manifold. Such representations are useful when data classes or clusters are well described by the span of a few samples. Classical Grassmannian kernels, including the projection and Binet-Cauchy kernels, require full Gram matrices, which leads to prohibitive computational and memory costs for large high-dimensional subspace datasets. We address this limitation using random features based on rank-one projections of subspace projection matrices followed by bounded non-linear transforms, either periodic or binary, to control the resulting distributions. We show that inner products in the random feature space approximate well-defined rotation-invariant Grassmannian kernels that depend only on the principal angles between subspaces. When the number of features is sufficiently large relative to the intrinsic subspace dimension, the approximation holds uniformly over all fixed-dimensional subspaces with high probability. For periodic transforms, the approximated kernel has a closed-form expression with tunable behaviour between inverse Binet-Cauchy and Gaussian-type regimes. Binary transforms yield compact one-bit subspace features, although no closed-form kernel is known. Structured rank-one projections based on randomised fast Fourier transforms further reduce computation without sacrificing practical accuracy. Experiments on synthetic data and ETH-80 classification tasks show that these features accurately preserve Grassmannian geometry while reducing computation, memory, and storage. Rank-one embeddings therefore provide a practical and scalable alternative to classical Grassmannian kernels.

Abstract

Explore similar work

Random features for Grassmannian kernel approximation with bounded rank-one projections

Exact Schur-Sylvester Dimensionality Reductions for Non-Smooth Stochastic Complexity and Manifold Sampling

Kolmogorov-Arnold Classifier Systems as Universal Approximators