Subgroup Rank-1 Lattice for Practical High-dimensional Black-box Integral Approximation
A subgroup rank-1 lattice method speeds high-dimensional black-box integral estimates, including softmax attention, via FFT correlations.
The paper studies subgroup rank-1 lattices for estimating integrals of high-dimensional black-box functions, including kernel mean embeddings and the softmax kernel in self-attention. A Korobov generator of fixed multiplicative order lets both feature-map products be computed exactly with FFTs in O(n log m) time and O(n) memory. The authors prove a Korobov-space error rate of O(n^(-(alpha-1)/(m-1))) for prime m at least d+1. Empirically, the method beat Gaussian and orthogonal random features and scrambled Sobol and Halton points in 49 of 54 synthetic kernel settings and all 45 softmax-attention settings on nine datasets.
- Subgroup lattices reduce feature-map products to O(n log m) time and O(n) memory.
- Korobov worst-case error decays as O(n^(-(alpha-1)/(m-1))) for prime m at least d+1.
- It beat random features and QMC points in 49 of 54 kernel settings.
- It won all 45 softmax-attention settings across nine real datasets.
- A d=2048 sample set of about 41 million points was built in 2.3 ms.
From the original article
1 min read at arxiv.orgEstimating 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.
By Yueming Lyu · arxiv.org
A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.