Subgroup rank 1 lattices speed up high dimensional integral estimates
Subgroup Rank-1 Lattice for Practical High-dimensional Black-box Integral Approximation
Machine Learning
Summary
Estimating the average of complicated functions with many inputs is important for machine learning but can be slow and use a lot of memory. The authors show a new way to choose points for these estimates, called subgroup rank-1 lattices, that lets computers perform calculations much faster and with less memory. They prove mathematically that this new method gives accurate results and demonstrate that it works better than other common methods on many tests. This technique can handle very large problems in milliseconds.
What this means in practice
- •For machine learning engineers: Build faster kernel approximations and softmax attention mechanisms for models with very high-dimensional inputs using efficient point sets.
- •For data scientists: Improve the speed and accuracy of black-box integral estimations for complex models on large datasets with reduced memory use.
Authors
Yueming Lyu
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.