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

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 $\Psi (X{)}^{\top }v$ or $\Psi (X)w$ for an elementwise nonlinearity $\Psi$ 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 $⟨t⟩$ reduces both maps to short cyclic correlations evaluated by FFT, giving exact results for arbitrary $\Psi$ 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 ${\Phi }_m$, the squared worst-case error in the Korobov space decays as $O(n^{-(\alpha -1)/(m-1)})$ for prime $m\ge d+1$, and this threshold is exact. Using the splitting of $n$ in $\mathbb{Q}({\zeta }_m)$, averaging over the $m-1$ admissible generators improves the constant by a factor $\Theta (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\approx 4.1\times 10^7$ in 2.3 ms.