Timezone: »

 
Poster
Subgroup-based Rank-1 Lattice Quasi-Monte Carlo
Yueming LYU · Yuan Yuan · Ivor Tsang

Tue Dec 08 09:00 PM -- 11:00 PM (PST) @ Poster Session 2 #662
in Poster Session 3 »
Quasi-Monte Carlo (QMC) is an essential tool for integral approximation, Bayesian inference, and sampling for simulation in science, etc. In the QMC area, the rank-1 lattice is important due to its simple operation, and nice property for point set construction. However, the construction of the generating vector of the rank-1 lattice is usually time-consuming through an exhaustive computer search. To address this issue, we propose a simple closed-form rank-1 lattice construction method based on group theory. Our method reduces the number of distinct pairwise distance values to generate a more regular lattice. We theoretically prove a lower and an upper bound of the minimum pairwise distance of any non-degenerate rank-1 lattice. Empirically, our methods can generate near-optimal rank-1 lattice compared with Korobov exhaustive search regarding the $l_1$-norm and $l_2$-norm minimum distance. Moreover, experimental results show that our method achieves superior approximation performance on the benchmark integration test problems and the kernel approximation problems.
Keywords: Submodular Optimization · Optimization

Author Information

Yueming LYU (University of Technology Sydney)
Yuan Yuan (MIT)
Ivor Tsang (University of Technology, Sydney)

More from the Same Authors