Finding the “Goldilocks” Solution to a Classic Math Problem: A Breakthrough in Numerical Integration
Imagine forecasting weather patterns, designing safe airplanes, or testing new medications — each relies on weighing countless possibilities, a task driven by numerical integration. Numerical integration is a mathematical concept that appears in many different fields — science, engineering, finance, and more. In simple terms, it is about finding the average value or total “area under the curve” for a complicated function, often with the condition that one can only sample the function at particular points. To address this, mathematicians have historically developed two main ways to estimate an integral: in the Monte Carlo (MC) method, the function can be sampled at random points to take the average. In Quasi-Monte Carlo (QMC) methods, points for evaluating the function are carefully and deterministically selected to be spread as uniformly as possible, which allows the error to shrink faster as more points are added. Despite the QMC methods improving error-shrinking rate, the MC method is often still preferred in real-world applications due to its flexibility and adaptability to different functions.
“QMC’s lack of flexibility is a problem,” UChicago Department of Computer Science Assistant Professor Haotian Jiang said. “For example, say you want to study the efficiency of a new medicine on people. You would have to recruit subjects to test this medicine on, and the only way you could do that is through a random sample from the population. You cannot create a person, so you cannot use QMC to simulate this study.”
In addition to not being as widely applicable as MC methods outside of a theoretical context, QMC falls short because of the lack of randomness in the starting point set. Some functions are like gentle hills, easy to map. Others are jagged and unpredictable, and QMC struggles when the landscape gets bumpy. In a classic result called the Koksma-Hlawka inequality, QMC methods were found to perform poorly and have increased error on functions that are not smooth, or functions with high Hardy-Krause variation — a measure of a function’s “wildness”.
This dilemma, in which there is a trade-off between optimizing the error-shrinkage (QMC) and the flexibility to accommodate for the unpredictability of the function (MC), is what Jiang and his collaborator from the University of Michigan, Nikhil Bansal, address in their recent paper, Quasi-Monte Carlo Beyond Hardy-Krause. Their new method means analysts in fields like finance may soon achieve more accurate results, while maintaining the flexibility to adapt to unexpected scenarios.
Jiang and Bansal’s work grew out of a deep motivation to develop a “Goldilocks” method, one as flexible as MC and as powerful as QMC in solving numerical integration problems. At the heart of QMC is the need for a “low-discrepancy” point set — think of planting seeds evenly in a field, where the fewer bare patches, the lower the discrepancy. To achieve a low-discrepancy point set, one could either use continuous discrepancy to design the point set from scratch (what QMC currently does) or use combinatorial discrepancy and divide a randomly generated set of points into two groups that are as uniform to each other as possible. The transference principle is a mathematical principle that links these two fundamental approaches to discrepancy: a good algorithm for the combinatorial problem can be used to create a solution for the continuous problem by taking a large cloud of random points to iteratively split it into a highly uniform subset.
“Let’s start with a much bigger number of samples. Using the combinatorial discrepancy method, we split them into two equal parts,” Jiang explains. “You can keep doing this until you reach the desired number of samples, by using this algorithm for splitting points iteratively. Ultimately, you get to a point where each point set is at the size you desire and uniformly distributed.”
However, although the transference principle has been a cornerstone in the literature since the 1970s, many known combinatorial discrepancy methods were computationally slow or only existed in theory, making it difficult to overcome the bottleneck with the transference principle. From 2016 through 2018, the first efficient algorithms for splitting points randomly while attaining low discrepancy at the same time emerged in a line of work. Efficiency was relative, however, and the algorithms were still not fast enough to achieve the levels of large-scale usage required for the iterative nature of the transference principle. In 2021, another group was able to improve upon the efficiency of these algorithms to create a simpler and faster version that performs the split and incorporates randomness. Using this efficient algorithm and applying the transference principle, Jiang and Bansal were able to create a method that splits a large pool of random samples into a group of different QMC point sets, each of which has low discrepancy (structural uniformity) and is sufficiently random, avoiding the pitfalls of the original QMC method. This lays the groundwork for more robust simulations — crucial for everything from climate predictions to setting insurance rates.
“These latest combinatorial discrepancy algorithms that smartly split points with randomness were not theoretically optimal, and we have been trying to improve them for years,” Jiang recalled. “While we haven’t succeeded in this effort yet, we managed to take these latest ideas in discrepancy theory and applied them in a new way. Suddenly, the pieces came together, and the results were very surprising – they improved upon the Koksma-Hlawka inequality, a benchmark used in QMC for over 60 years. ”
The method was recognized by peers with a Best Paper Award. It keeps the adaptability of MC while meeting—or exceeding—the traditional performance measures of QMC, especially on functions with lots of ‘rough edges’ or noise. What came as a surprise to the authors was that they were also able to improve the Hardy-Krause variation to a much smaller variation, which they call the “smoothed-out” variation. The Koksma-Hlawka inequality used the Hardy-Krause variation to evaluate QMC methods because QMC was terrible at handling high-frequency noise. However, because the new algorithm is robust to this kind of noise, the new smoothed-out variation achieves a tighter error bound for the algorithm by putting less weight on the noise.
Jiang is now working on improving the efficiency of this algorithm and working with experts at the Illinois Institute of Technology to conduct preliminary testing to implement this algorithm in real-world contexts. He is hoping to reduce the number of points the algorithm has to start on from n^2 to a lower value, such as 2n. He is also hoping to tackle other problems through the lens of discrepancy theory and rethinking how algorithms have been designed. If successful, these refinements could unlock faster, more reliable algorithms and analysis in AI and any field where uncertainty meets big data.
Jiang is currently recruiting prospective PhD students to his lab. To learn more about his work, please visit his website here.
