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

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∈ℝn× 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,td-1) uses a scalar t of fixed multiplicative order m. Splitting mathbbFn^× into cosets of langle trangle reduces both maps to short cyclic correlations evaluated by FFT, giving exact results for arbitrary Psi in O(nlog 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 Phim, the squared worst-case error in the Korobov space decays as O(n-(α-1)/(m-1)) for prime m≥ d+1, and this threshold is exact. Using the splitting of n in mathbbQ(zetam), 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≈4.1×107 in 2.3 ms.