Tractability Properties of High-Dimensional Integration and Star Discrepancy / submitted by Andreas Thoma

Kinjal Basu

Leszek Plaskota, G.W. Wasilkowski

Josef Dick, Friedrich Pillichshammer

Erich Novak, H. Woźniakowski

Introduction There has been an increasing interest in studying computational aspects of high dimensional problems. Such problems are defined on spaces of functions of d variables and occur in many applications, with d that can be hundreds or even thousands. Examples include: • High dimensional integrals or path integrals with respect to the Wiener measure . These are important for many applications, in particular, in physics and in finance. High dimensional integrals also occur when we want to compute certain parameters of stochastic processes. Moreover, path integrals arise as solutions of partial differential equations given, for example, by the Feynman–Kac formula . See [25, 40, 66, 82, 85, 91]. • Global optimization where we need to compute the (global) minimum of a function of d variables. This occurs in many applications, for example, in pattern recognition and in image processing , see [97], or in the modelling and prediction of the geometry of proteins, see [45]. Simulated annealing strategies and genetic algorithms are often used, as well as smoothing techniques and other stochastic algorithms, see [10] and [74]. Some error bounds for deterministic and stochastic algorithms can be found in [42, 43, 44, 48, 53]. • The Schrödinger equation for m > 1 particles in ℝ 3 is a d = 3m -dimensional problem.

Amir Sadikov

Low-discrepancy point sets and digital sequences underpin quasi-Monte Carlo (QMC) methods for high-dimensional integration. We cast two long-standing QMC design problems as program synthesis and solve them with an LLM-guided evolutionary loop that mutates and selects code under task-specific fitness: (i) constructing finite 2D/3D point sets with low star discrepancy, and (ii) choosing Sobol' direction numbers that minimize randomized QMC error on downstream integrands. Our two-phase procedure combines constructive code proposals with iterative numerical refinement. On finite sets, we rediscover known optima in small 2D cases and set new best-known 2D benchmarks for N >= 40, while matching most known 3D optima up to the proven frontier (N <= 8) and reporting improved 3D benchmarks beyond. On digital sequences, evolving Sobol' parameters yields consistent reductions in randomized quasi-Monte Carlo (rQMC) mean-squared error for several 32-dimensional option-pricing tasks relative to widely used Joe--Kuo parameters, while preserving extensibility to any sample size and compatibility with standard randomizations. Taken together, the results demonstrate that LLM-driven evolutionary program synthesis can automate the discovery of high-quality QMC constructions, recovering classical designs where they are optimal and improving them where finite-N structure matters. Data and code are available at https://github.com/hockeyguy123/openevolve-star-discrepancy.git.

Fred J. Hickernell, Xiaoqun Wang

Dimensionally unbounded problems are frequently encountered in practice, such as in simulations of stochastic processes, in particle and light transport problems and in the problems of mathematical finance. This paper considers quasi-Monte Carlo integration algorithms for weighted classes of functions of infinitely many variables, in which the dependence of functions on successive variables is increasingly limited. The dependence is modeled by a sequence of weights. The integrands belong to rather general reproducing kernel Hilbert spaces that can be decomposed as the direct sum of a series of their subspaces, each subspace containing functions of only a finite number of variables. The theory of reproducing kernels is used to derive a quadrature error bound, which is the product of two terms: the generalized discrepancy and the generalized variation. Tractability means that the minimal number of function evaluations needed to reduce the initial integration error by a factor ε \varepsilon is bounded by C ε − p C \varepsilon ^{-p} for some exponent p p and some positive constant C C . The ε \varepsilon -exponent of tractability is defined as the smallest power of ε − 1 \varepsilon ^{-1} in these bounds. It is shown by using Monte Carlo quadrature that the ε \varepsilon -exponent is no greater than 2 for these weighted classes of integrands. Under a somewhat stronger assumption on the weights and for a popular choice of the reproducing kernel it is shown constructively using the Halton sequence that the ε \varepsilon -exponent of tractability is 1, which implies that infinite dimensional integration is no harder than one-dimensional integration.