A research team, including Nathan Kirk from the Illinois Institute of Technology, has introduced a new method that uses machine learning to improve quasi-Monte Carlo methods. This approach is detailed in the paper “Message-Passing Monte Carlo: Generating Low-Discrepancy Point Sets Via Graph Neural Networks,” published in the Proceedings of the National Academy of Sciences.

Kirk explains the concept using an analogy: “Imagine a large, perfectly square lake. One morning, 10 fishing boats head out onto the water. If the fishermen do not coordinate and randomly choose their positions on the lake, they might run into problems. Some boats may end up too close together, competing for the same fish, while other areas of the lake could remain completely unfished. However, if the fishermen communicate and plan their positions strategically, they could cover the lake uniformly, maximizing their chances of catching the most fish and ensuring an efficient spread across the water.”

The Message-Passing Monte Carlo (MPMC) method generates low-discrepancy point sets using graph neural networks (GNN). These networks are adept at capturing relationships between points in a graph structure. Kirk states: “The goal is to generate point distributions that minimize irregularity across a space.”

The research demonstrates MPMC's superiority over previous methods in computational finance by achieving a 25-fold improvement when estimating financial derivatives' prices. The study's co-authors include T. Konstantin Rusch and Daniela Rus from Massachusetts Institute of Technology.

“One big challenge of using GNNs and [artificial intelligence] methodologies is that the standard uniformity measure, called ‘star-discrepancy,’ is very slow to compute,” says Kirk. To address this issue, they switched to L2-discrepancy and developed a technique focusing on significant interactions among points.

MPMC has potential applications in various fields such as computer graphics and robotics. In graphics, it can enhance rendering techniques by improving light simulation and texture mapping. For simulations, it allows more precise approximations with fewer samples.

Kirk concludes: “The most exciting aspect about this project for me was merging two personal academic interests, Monte Carlo methods and machine learning.” He highlights MPMC as "the first machine learning approach to generate low-discrepancy point sets" within quasi-Monte Carlo methods.