Computational Mathematics Seminar by Yueming Lyu: Subgroup Rank-1 Lattices for Practical High-Dimensional Black-Box Integral Approximation
Speaker: Yueming Lyu, senior research scientist, Centre for Frontier AI Research (CFAR), Agency for Science, Technology and Research (A*STAR), Singapore
Title: Subgroup Rank-1 Lattices for Practical High-Dimensional Black-Box Integral Approximation
Abstract:
Many problems in machine learning come down to estimating a high-dimensional integral of a black-box function. Examples include expectations, normalizing constants, kernel mean embeddings, and the softmax kernel inside linear-time attention for large language models. Quasi-Monte Carlo (QMC) methods suit this setting well. They need no gradients, they evaluate the integrand on a point set fixed in advance, and they often beat random sampling. In practice, though, the n QMC points serve as a design matrix X ∈ ℝ^{n×d} for a feature map. Applying a nonlinearity elementwise and then aggregating costs O(nd) time and memory for every standard point set, which becomes the bottleneck when both n and d are large.
This talk is about subgroup rank-1 lattices. These are Korobov-type lattice rules whose generator (1, t, …, t^{d−1}) uses a scalar t of fixed multiplicative order m, independent of n. Classical component-by-component constructions never produce such generators. I will show that giving up this freedom pays off in three ways.
- Computation. Splitting the multiplicative group mod n into cosets of ⟨t⟩ turns the lattice transform into short cyclic correlations. These are evaluated by FFT, so the transform is computed exactly for any nonlinearity in O(n log m) time and O(n) memory, without ever forming X.
- Theory. Using resultants with the cyclotomic polynomial Φ_m, I prove that for prime m ≥ d+1 the worst-case error in the Korobov space converges. This threshold is sharp: for m ≤ d the error has an n-independent floor. Using the complete splitting of n in ℚ(ζ_m), I also show that averaging over the m−1 admissible generators improves the constant by a factor Θ(m−1).
- Practice. On kernel estimation and on softmax attention over real embedding datasets, the method is more accurate than random features, orthogonal random features, and scrambled Sobol’ and Halton points in almost every setting tested. At d = 2048 it builds a 41-million-point sample set in 2.3 ms.
Bio:
Yueming Lyu is a Senior Research Scientist at the Centre for Frontier AI Research (CFAR), Agency for Science, Technology and Research (A*STAR), Singapore. He received his Ph.D. degree from the University of Technology Sydney (UTS), Australia, and his B.E. and M.E. degrees from South China University of Technology, China.
His research interests lie in machine learning and optimization, with a particular focus on quasi-Monte Carlo methods, black-box optimization, and kernel methods. He has published over 20 papers in top-tier machine learning journals and conferences, including IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), International Conference on Machine Learning (ICML), Advances in Neural Information Processing Systems (NeurIPS), and International Conference on Learning Representations (ICLR).
He regularly serves as an Area Chair for premier machine learning conferences, including ICML, NeurIPS, and ICLR, and as a Program Committee member for AISTATS, AAAI, and IJCAI. He also serves as a reviewer for leading journals, including TPAMI, Transactions on Machine Learning Research (TMLR), International Journal of Computer Vision (IJCV), Journal of Artificial Intelligence Research (JAIR), IEEE Transactions on Neural Networks and Learning Systems (TNNLS), and Machine Learning.