Hickernell_HDA_2025_Talk_2025_Sep_12-ver-25-09-12-ver-b.pdf

Transcript

1. Fred J. Hickernell, Illinois Institute of Technology High Dimensional Approximation, Sep 12, 2025 The Quality of Extensible Lattice and Kronecker Sequences • Joint work with Claude Hall, Jr. Larysa Matiukha, Jimmy Nguyen, Alexander Pride, and the QMCPy team • Thanks to US National Science Foundation #2316011 • Thanks to the organizers Slides at speakerdeck.com/fjhickernell/hda-2025
2. of 23 Google AI says this about dropping the first point of a low discrepancy sequence Dropping the fi rst point in a low-discrepancy sequence like the Sobol sequence is generally a bad idea because it breaks the sequence's balance and properties, potentially being "very detrimental" to the resulting estimates, though some techniques like scrambling or a speci fi c context like transforming to a Gaussian distribution might warrant considering changes to the initial points. For instance, if the original Gaussian point is in fi nite after a transformation, skipping it might be necessary, but it requires fi nding better remedies than simply skipping the point. 2
3. of 23 Motivation • Extensible lattice and digital sequences have preferred sample sizes of • IID samples have no preferred sample sizes • How well can we do by constructing extensible lattice and Kronecker sequences that are - Good for all and ? - An alternative to Halton or digital sequences? • Why? - Run out of time - Missing data n = 1, b, b2, … n = 1, 2, 3,… d = 1, 2, 3,… 3
4. of 23 4 100 101 102 103 104 105 106 n 10°6 10°5 10°4 10°3 10°2 10°1 100 RMS Discrepancy d = 13, ∞ = (1.00, 0.25, 0.11, 0.06, 0.04, 0.03, . . . ) IID CBC Kronecker CBC lattice O(n°0.87) Sneak Preview
5. of 23 xi = ϕb (i)ζ + Δ mod 1 ζ ∈ ℕd, Δ ∈ [0,1)d ϕb is van der Corput xi = iζ + Δ mod 1 ζ, Δ ∈ [0,1)d Shifted Lattice and Kronecker Sequences 5 0.00 0.25 0.50 0.75 1.00 xi1 0.00 0.25 0.50 0.75 1.00 xi2 n = 25, 64 0.00 0.25 0.50 0.75 1.00 xi1 0.00 0.25 0.50 0.75 1.00 xi2 n = 25, 64, 97
6. of 23 What we know • Any nodes for integration for , using equal sample weights do no better than error [H, Kritzer, Kuo, Nuyens 2012] • Good lattice by component-by-component (CBC) constructions for and [Nuyens & Cools, 2006], [Dick, Kuo, Sloan 2013] • Kronecker - [Richtmyer 1951] - [Dick, Goda, Larcher, Pillichshammer, Suzuki 2025] n = 1, 2, 3,… 𝒪 (n−1) ζ d = 1, 2, … n = 1, b, b2, … ζ ( 2, 3, 5, …) mod 1 (21/(d+1), …,2d/(d+1)) mod 1 6
7. of 23 Sequence quality Discrepancy = worst-case cubature error 
 = deviation of the empirical distribution from the target distribution • Di ff erent choices of Banach or Hilbert space yield di ff erent discrepancies • We choose a convenient D({xi }n−1 i=0 , ℱ) := sup ∥f∥ℱ ≤1 ∫ [0,1]d f(x) dx − 1 n n−1 ∑ i=0 f(xi ) ℱ ℱ 7
8. of 23 Periodic integrands For lattices with , there exists with [H & Niederrieter 2003] For , there exists with [Matiukha, Ding & H 2025+] ∥f∥ℱα,∞ := sup k∈ℤd ([ d ∏ ℓ=1 max(1,[γ−1 ℓ |kℓ |]α)] ̂ f(k) ) , smoothness α > 1 n = b, b2, … ζ D({xi }n−1 i=0 , ℱα,∞ ) ≤ C(α, γ, ϵ, d)n−α(log n)α(d+1)[log log(n + 1)]α(1+ϵ) n = 2, 3,… ζ <latexit sha1_base64="AZKovyt3dhJTNo+7G1MuEiLEX6c=">AAAG63icdVRRb9s2EFa81uvcbms27GkvxLwW9qoEllenBoYCRZqsQ4GhWbG0aUPHoCTKJkKRAkm7Fgj+ir0Ne+1r/0//zU6K1NqOTRg09X3fHY+8O4YZZ9r0eh93Gl/cuNn88tZXrdt3vv7m27u7373ScqYiehpJLtVZSDTlTNBTwwynZ5miJA05fR1ePi3413OqNJPib5NndJSSiWAJi4gBaLy78wGHdMKEJZxNxC+uddTBFoeSxzpP4c8u3JhhN7bscc9dWLEXOB+nxEx1pOzvgGPCsynxMROJyV0X3cecotbTToWjZV94QtKUOABpphmXwkdxF+FEkciG4NkGaA+FFzbYu7J2DlXRHcKWii0chnOl2dSKCwt6oDGqIczh1DG5qCICT+Cw0NW+QE1F/MkV2LbuIzzVGYmoHdACMSylGnUwlxMkurWrTvwg6Dp0XsLF1BEAjD7RwYP6PF2H1yP+HJ+hC2OJyJFDwi0FLtBjVAUPh8/Ww2yVn3V6xnfbvf1eOdD1RVAt2l41Tsa7N37GsYxmKRUm4kTr86CXmZElyrCIU9fCM03hCi7JhNop5XNqAFNU0HeRhGzB3jghKeN5TBMy48ZZrJN6vWK9KMsRMGChHMsve0lzIQ19pkju7Mtnh84OB375c+geag/K0cLXxRvdHPIZrdz0/CAY+sHwYLPyJY0rYTAM/P6vfm+z7g3lXL6rpP3BwO8Hj/zBFvELRcSkDqD/sA8hPCwdL90CSXVR7nC6sk3WuQLcyKVwn0xBKKso6JRONJhkSs5ZDPVZtd+y7nxmkuHIMpHNDBURqIFLZhwZiYq2RzFTNDI8hwWJFIPco2hKoPEMPA4rO4ZSXhoSaohjuQauitWdByNr8YactKEd10xUvM2kTM4Gi3zrJnWaNhhJtc2oTldldEShART9E67vRUYVMaDEc6KcLaYtfCTnzhbTFj7VsEExbeFVKVBXiuWwT5QMoZeKZIahPVk/1fHiM3m8TsYsqViV2nidnZ+5lSf87Jrg7argrXPwrgTrr8j1xav+fnCwf/BXv/3kefXC3PJ+9H7yOl7gPfKeeH94J96pFzV+aPzWOGocN9PmP81/m/9dSRs7lc333spovv8fyD506A==</latexit> D({xi }n→1 i=0 , Fω,↑) → C(ω, ω, ε, d) b ↑ 1 1 ↑ b1→ω n→1 ϑω→1n→ω ↓ (log n)ω(d+1)[log log(n + 1)]ω(1+ε) any n n = ϑbp 8
9. of 23 Periodic integrands For , there exists with [Matiukha, Ding & H 2025+] Proof by noting that the fi rst points of a lattice are the union of lattices ∥f∥ℱα,∞ := sup k∈ℤd ([ d ∏ ℓ=1 max(1,[γ−1 ℓ |kℓ |]α)] ̂ f(k) ) , smoothness α > 1 n = 2, 3,… ζ <latexit sha1_base64="AZKovyt3dhJTNo+7G1MuEiLEX6c=">AAAG63icdVRRb9s2EFa81uvcbms27GkvxLwW9qoEllenBoYCRZqsQ4GhWbG0aUPHoCTKJkKRAkm7Fgj+ir0Ne+1r/0//zU6K1NqOTRg09X3fHY+8O4YZZ9r0eh93Gl/cuNn88tZXrdt3vv7m27u7373ScqYiehpJLtVZSDTlTNBTwwynZ5miJA05fR1ePi3413OqNJPib5NndJSSiWAJi4gBaLy78wGHdMKEJZxNxC+uddTBFoeSxzpP4c8u3JhhN7bscc9dWLEXOB+nxEx1pOzvgGPCsynxMROJyV0X3cecotbTToWjZV94QtKUOABpphmXwkdxF+FEkciG4NkGaA+FFzbYu7J2DlXRHcKWii0chnOl2dSKCwt6oDGqIczh1DG5qCICT+Cw0NW+QE1F/MkV2LbuIzzVGYmoHdACMSylGnUwlxMkurWrTvwg6Dp0XsLF1BEAjD7RwYP6PF2H1yP+HJ+hC2OJyJFDwi0FLtBjVAUPh8/Ww2yVn3V6xnfbvf1eOdD1RVAt2l41Tsa7N37GsYxmKRUm4kTr86CXmZElyrCIU9fCM03hCi7JhNop5XNqAFNU0HeRhGzB3jghKeN5TBMy48ZZrJN6vWK9KMsRMGChHMsve0lzIQ19pkju7Mtnh84OB375c+geag/K0cLXxRvdHPIZrdz0/CAY+sHwYLPyJY0rYTAM/P6vfm+z7g3lXL6rpP3BwO8Hj/zBFvELRcSkDqD/sA8hPCwdL90CSXVR7nC6sk3WuQLcyKVwn0xBKKso6JRONJhkSs5ZDPVZtd+y7nxmkuHIMpHNDBURqIFLZhwZiYq2RzFTNDI8hwWJFIPco2hKoPEMPA4rO4ZSXhoSaohjuQauitWdByNr8YactKEd10xUvM2kTM4Gi3zrJnWaNhhJtc2oTldldEShART9E67vRUYVMaDEc6KcLaYtfCTnzhbTFj7VsEExbeFVKVBXiuWwT5QMoZeKZIahPVk/1fHiM3m8TsYsqViV2nidnZ+5lSf87Jrg7argrXPwrgTrr8j1xav+fnCwf/BXv/3kefXC3PJ+9H7yOl7gPfKeeH94J96pFzV+aPzWOGocN9PmP81/m/9dSRs7lc333spovv8fyD506A==</latexit> D({xi }n→1 i=0 , Fω,↑) → C(ω, ω, ε, d) b ↑ 1 1 ↑ b1→ω n→1 ϑω→1n→ω ↓ (log n)ω(d+1)[log log(n + 1)]ω(1+ε) any n n = ϑbp n = n0 + n1 b + ⋯ + nm bm 9
10. of 23 Periodic integrands For lattices with and , there exists with [H & Niederrieter 2003] For , there exists with [Matiukha, Ding & H 2025+] ∥f∥ℱα,∞ := sup k∈ℤd ([ d ∏ ℓ=1 max(1,[γ−1 ℓ |kℓ |]α)] ̂ f(k) ) , smoothness α > 1 n = b, b2, … ∑ γℓ < ∞ ζ D({xi }n−1 i=0 , ℱα,∞ ) ≤ C(α, γ, δ)n−α+δ n = 2, 3,… ζ <latexit sha1_base64="ynX99p6gH1DYW/6x0+cYmycQqtE=">AAAHDXichVRLbxs3EF6rqZKqj8TtsRciagOnXRuiGtk6JEDgJE1RoIgb1IkTUxa4u1yJMJe7IbmKFgR/Q39Nb0Wvvfbaf9PZh2JJllBCoLjzffPicCbIBNem1/t3p/XRjY/bN2990vn0s8+/uH1n98tXOs1VyE7DVKTqLKCaCS7ZqeFGsLNMMZoEgr0OLp+U+OsZU5qn8jdTZGyU0InkMQ+pAdF4d+cfErAJl5YKPpHfuc7TPWJJkIpIFwn82bkbc+LGlj/quQsr97HzSULNVIfK/ghyQkU2pT7hMjaFu4/uEcFQ58leI0fLtsiEJgl1IIyYMPQ+IrGioQ3AqMVoHwUXFu/Xis6hJrBj8Kb43BFIKcmmVl7Yffx9baFkEbRAiIC8I3rRxAQGwVrNq7Rq8QdV0GUy+mAfLHXQPUTevctptO78yodhc2OpLJBDEhJBtYDHyBGdJ6hOEa6FCeEWkTj0EDUXtBSuRI9QEzJknvnof6xdGVkLvFN9Lgo4vtPtHfSqha4fcHPoes06Ge/e+IZEaZgnTJpQUK3PcS8zI0uV4aFgrkNyzTIaXtIJs1MmZsyATDHJ3ocphAe+SUwTLoqIxTQXxlmi48V5RXtePViQAQoPtvqyl6yQqWHPFS2cffn82NnhwK9+Dn2LuoNqdch18kYzxyJnjZmej/HQx8PDzcyXLGqIeIj9/g9+bzPvDVx++r6h9gcDv4+P/MEW8gtF5WQRQP9BH0J4UBleugWa6LIhILuqkdaxUrgRS+A+uYJQVqXAUzrWoJKpdMYjplHToMu889zEw5HlMssNkyGwAYtzgUyKysGAIq5YaEQBBxoqDrVH4ZRCfxoYHysegzS9NDTQEMfyG6iftTvHI2vJhpp0MfTcqoqKtqlUxdmgUWx1sijTBqVUbVNalKtResqgART7Ba7vRcYUNcAkM6qcLbcteJjOnC23LXiiwUG5bcFVRVA1YznsE5UG0EtlMYPAnqxn9Wx+BT5bByMeN6hKbLSOzs7cypA/u0Z4u0p46xzMFbw+Ra4fXvUP8OHB4a/97uOfmwlzy/vau+vtedg78h57P3kn3qkXto5ao1bcmrR/b//R/rP9V01t7TQ6X3krq/33f+8ZhGE=</latexit> D({xi }n→1 i=0 , Fω,↑) → C(ω, ω, ε) b ↑ 1 1 ↑ b1→ω n→1+ε ϑω→1→εn→ω+ε any n, if ϖω ϑ < ↓ n = ϑbp, if ϖϑ < ↓ 10
11. of 23 Expected Squared Discrepancy A symmetric, positive de fi nite de fi nes a discrepancy: For a random shift, K : [0,1]d × [0,1]d → ℝ D2({xi }n−1 i=0 , K) := ∫ [0,1]d×[0,1]d K(t, x) dtdx − 2 n n−1 ∑ i=0 ∫ [0,1]d K(xi , x) dx + 1 n2 n−1 ∑ i,j=0 K(xi , xj ) Δ ∼ 𝒰 [0,1)d <latexit sha1_base64="0dvSkPGW3Bgqb6qZVNR/SU9Uwu0=">AAAIFHiclVVdb9s2FFXjbu68r6Z93Asxb0WyqYGl1akxoEPRJeiwYGhWLG1ayzEoibLZUKJGUk48gn9jv2Zvw173Ouzf7EpWUkuWgFUwZJrnnMv7xWs/ZVSqweDfG1udm++93731Qe/Djz7+5NPb23deSJ6JgJwEnHFx6mNJGE3IiaKKkdNUEBz7jLz0z7/P8ZcLIiTlyS9qmZJJjGcJjWiAFWxNt7f+8Xwyo4nGjM6Sr0zPi7Ga+74+NMjz6YyND87cHU97PmehXMbwpS/NlKKv0fqWd0CYwrkk5mEFcYxnppo+Gpgzndx3jH20WxgWE9S7hx6hXrP9msi7oCGZY6WPDMi9nqfIpdIXcyIIglPfojvrhpSxUdXwLrqHvoVTPZqoqR4PbGdyFhp0VJPVols2B2ajXtX6/5NBAOBWnmYR69BsSH7NMEiKAD0oY5zOdUoE5SH9jQAdvM0z8O5pQ3m676Nq7HAQjYlE16l4l1y2xwEpbINWaYoEDiAXOjlzAZZZDH7bb649b3Wj6L26J9M3aBdqQZLwuo1709v9wd6geNDmwikXfat8jqfbN7/wQh5kMUlUwLCUY2eQqonGQtGAEbgZmSQpDs7xjOg5YQuiYE+QhFwEPI4xHO5FOKZsGZIIZ0wZ7cnoal1RXxb3FvYAhXtb/NLnZJlwRZ4KvDT6+dMnRo+GdvEx6EvUHxZPz9skN5p5wjJSmoHKOiPbGe03M59DU62Izsix3W/sQTPvFWGMX5RUdzi0XeehPWwhPxM4mV054D5wwYUHheG1LOBY5hWE6PJGkXUs32zEYsgnFeBKdTdvNhlJkKSCL6B7JCq0gVjnjTMVjSaaJmmmSBIAG7AoY0hxlM9HFFJBAsWWsMCBoFB7FMwxdKuCKVo50ef8XGFfgh/rPbC6smbsTLT2GmrSd4ypSUTYJimK06BYth5yVaYGERdtoqtylaIDAhdAkJ8gfc9g9GAFTG+BhdH5qwUP+MLo/NWCxxIOyF8tuCgIYsVYd/tYcB/uUvm/dFyP6vDyLXhYB0MalWgxiGro4tRUJujpBuF1lfDaGJgrTn2KbC5euHvO/t7+z27/8Y/lhLllfWZ9bu1YjvXQemz9YB1bJ1bQ+a4TduJO0v29+0f3z+5fK+rWjVJz16o83b//A3Ry5QI=</latexit> E D2({xi + ! mod 1}n→1 i=0 , K) = D2({xi }n→1 i=0 , K) where K(t, x) := [0,1]d K(t + y mod 1, x + y mod 1) dy periodized K D2({xi }n→1 i=0 , K) = → [0,1]d↑[0,1]d K(t, x) dtdx + 1 n2 n→1 i,j=0 K(xi, xj) 11
12. of 23 Expected Squared Discrepancy A symmetric, positive de fi nite de fi nes a discrepancy: For a random shift, K : [0,1]d × [0,1]d → ℝ D2({xi }n−1 i=0 , K) := ∫ [0,1]d×[0,1]d K(t, x) dtdx − 2 n n−1 ∑ i=0 ∫ [0,1]d K(xi , x) dx + 1 n2 n−1 ∑ i,j=0 K(xi , xj ) Δ ∼ 𝒰 [0,1)d <latexit sha1_base64="7Y4joSv0Sal4ndHU0MpLCWho7io=">AAAII3icjVVbb9s2FFbjbu68W7M97oWYtyLZ1EDS6tQYUKDoEnRYUTQrljar6RiURNlsqEtJyrHB8efs1+xt2Mse9rrfsSNFaS1FCkYYMsXv+86FhzzyM86kcpy/b2z1br73fv/WB4MPP/r4k09vb3/2Qqa5COhxkPJUnPhEUs4SeqyY4vQkE5TEPqcv/bMfCvzlkgrJ0uQXtc7oNCbzhEUsIAqWZttb/2KfzlmiCWfz5BszwDFRC9/XhwZhn8355ODU28Ea+ykP5TqGP70yM4a+RZtL+IByRQpJnIY1xDXYzDR74JhTndx1jf1ktzQspmhwBz1Agw77DRU+ZyFdEKWfGNDjUnoXIcwSNdMTx3anp+BXsZhKVL1CNO9EO5sOlLFR3SHYhKUidRHrQlljoy5oZYp9iAQJIE+dnHoAyzyGyO3Xb2PvDKPMsxnJ7DXaSBCnULyitqAd/F9XivGQtjorLDa9tZWsjAArulL6fEEFRXAurrG8ewd9D+F252lvvjpmF5J+8yYnYS2/CxubBb0+n+tqtoKAaRK+PdWD2e2hs+eUA12duNVkaFXjaLZ98yscpkEe00QFnEg5cZ1MTTURigWcgv1c0owEZ2RO9YLyJVWwJmhCz4M0jgk4xxGJGV+HNCI5V0ZjGV3Oa+pVeY1hDVDYivJNn9F1kir6WJC10c8fPzJ6PLLLn0Ffo+GoHAN8ldxq5hHPaWUGttYd2+54v535nIYV0R27tved7bTzfqWcp+cV1RuNbM+9b486yM8ESeaXAXj3PAjhXml4YxdILIviQXZFSWUTKxZbsRj2kwkIpb5aHAsZSZBkIl3CKZKo1AZikzfJVTSeapZkuaJJAGzAopwjlaKiXaKQCRoovoYJCQSD2qNgQeAWKmiqNY9+mp4p4kuIY/MMQCOOs4WZuFOtcUtNhq4xDYkIuyRlcVoU604nl2VqEaWiS3RZrkp0QOECCPoUtu9ZRgVRwMRLIowuHh14kC6NLh4deCzBQfHowEVJEBeMzbCPROrDXao+U0fNrA5X78DDJhiyqELLltFAlyem9h06uUJ4VSe8Mgb6itvsIlcnL7w9d39v/2dv+PCnqsPcsr6wvrR2LNe6bz20frSOrGMr6D3tyd5vPdP/vf9H/8/+XxfUrRuV5nOrNvr//Ad6Gulr</latexit> E D2({xi + ! mod 1}n→1 i=0 , K) = D2({xi }n→1 i=0 , K) = → [0,1]d↑[0,1]d K(t, x) dtdx + 1 n2 n→1 i,j=0 K(xi, xj) = →K + 1 n2 n→1 i,j=0 K(xi → xj mod 1) where K(x) := K(x, 0), K := [0,1]d K(x) dx 12
13. of 23 Expected Squared Discrepancy for Kronecker which leads to a weighted sum of for all up to is similar for all iζ + Δ mod 1, ζ ∈ [0,1)d, Δ ∼ 𝒰 [0,1)d ESD(n, ζ, Kron) = − K + 1 n2 n−1 ∑ i,j=0 ˜ K ((i − j)ζ mod 1) = − K + 1 n2 [n˜ K (0) + 2 n−1 ∑ k=1 (n − k)˜ K (kζ)] ESD(n, ζ, Kron) n N <latexit sha1_base64="+H+j+ofOc81hiDmHzK3/RmuTUps=">AAAGHnicjVRbb9MwFE5hhVFuGzzyElGQNlRNTVm3CglpGps2gdjGxraypVSOc9JFc+xgO92K5f/Cr+EN8Qqv/BKcNBW9SliVc3q+7zu+nHPsxSQUslr9Xbhxc6546/b8ndLde/cfPFxYfHQiWMIxHGNGGG96SAAJKRzLUBJoxhxQ5BE49S7fpPhpF7gIGf0oezG0ItShYRBiJI2rvfDH9aATUoVI2KEvtCvhWopAnR5tH23ppb2K7XqM+KIXmY9yv4JE2vgiJC94pN5xRvWyXXplv7ZdkURtRY3l6M9qTxshgSi+UNSYRpIHzsLS/wrrfkmQ3xeqkNp6EDCjYUTUvtngss4ZNouBZ4cSuuQC9QdHKrUXytWVajbsScPJjbKVj4P24twz12c4iYBKTJAQ5041li2FuAwxARM+ERAjfIk6oC6AdEEaHwcKV5hFETJruwGKQtLzIUAJkVq5IhjYI+rrLIPGZ1CTweyfuoQeZRJ2OOppdbizqVWjXsl+2n5ul+vZKLmT5KlhNkkCeZhqxXEaFaexNp15CH5OdBpOpfayUp3O+wSEsKucWqvXKzVnvVKfQd7niHYGG6it1swWVrPAQ7eAIpGWgjldmloxjqXOqVhk7jPkZiuj3rSKRCCMJOasG/og7EyL+TDvPJFBo2UqK04kUGzYBgsSYktmp51i+yEHLEnPGAjz0OTexheIIyxNP42s6DF2KZGXFt5wDfTrVZ87LaXcKTkpO1qPSbg/S5IlZ4qiN3ORQZqmiBifJRqkKxdtgWkADu/N9e1n/WWYbhdxrdJpBo5ZV6t0moFHwiyQTjNwnhF4nzG87QPOPN3vf89TB+On2r7+B26Pg34Y5Kh5YfxxtNs04NCT1JwgnI0SzrQ274oz/opMGie1FWdtZe1DrbzxNn9h5q0n1lNryXKsdWvD2rUOrGMLF3YLtHBVuC5+K34v/ij+7FNvFHLNY2tkFH/9BcRZLh8=</latexit> WSESD(N, ω, Kron) := N n=1 n ESD(n, ω, Kron) in O(N) operations ∑bm+1−1 n=bm n ESD(n, Kron) m 13
14. of 23 Expected Squared Discrepancy for Lattices , so ϕb (i)ζ + Δ mod 1, ζ ∈ ℕd, Δ ∼ 𝒰 [0,1)d, ϕb is van der Corput <latexit sha1_base64="1AOzFSX9U8NF/lufG0p9DuWCtXY=">AAAG/HichVRdb9s2FFXc1uu8bm26x70QM1bYqxJIXp0aGLIVXYMWK4qm3dKmDR2DkiibNUUKFOXEI7hfs4cBw173X/ZvdqXIqD9kjDBo6p5zL8/lJW+QcpZpz/t3p3Ht+o3mJzc/bX126/Mvbt/Zvfsmk7kK6UkouVSnAckoZ4KeaKY5PU0VJUnA6dtg+lOBv51RlTEpftXzlA4TMhYsZiHRYBrt7vyJAzpmwhDOxuJb28KaXmqVmKNfntiOcBEOJI+yeQJ/Bv9GNbFgS4ieAIcTbbuodQ+1DtEewhI2KnSY5xbdRzhWJES+Eec9i3CWJyPD3A+Hnj03Au35YLtgEdWMR4UDDtiYd1AHpxM2Cjqsu1etPnS7mxJAVSKjFW1FQIihQA/GIOl/FQF5zNEZEqtCOstBPUjvPqrUTw990B6cG8xDyjjCXI5HARJYFZ+2TAmOPUknBrdHojPt1udYJTbt1pxtlUIpTg1bmIpoUZnRnba375UDbS78atF2qnE82r3+PY5kmCdU6JCTLDvzvVQPDVGahZxCqfOMpiSckjE1E8pnVINNUUEvQpkkBLbGMUkYn0c0JjnX1uAsXqxXvC/Liwg2QOG4yy8zpXMhNX2qyNya108fWzPou+XPom9Qu1+OFt4k14Z5zHNahfFc3x+4/uCgnvmaRhXRH/hu7zvXq+e9o5zLi4ra6/fdnv/Q7W8hv1REjBcCeg96IOFBGXjpFEiSFcWE7Ir3ka1jhbEWS+A8mQIpq1bgaSl5tmlWWZxBpFTJGVyvDJUhQ7XMO8t1PBgaJtJcUxECG7A450hLVPQBFDFFQ83nsCChYnAlUDgh8EA0dIuVHQMpp5oEhY7lq3F11e2ZPzQG15Sq7Vu75qKibS5lzWo85ls3WVSvxkmqbU6LKlZOTyi8C0VfwPG9TKkiGph4RpQ1xbQFD+XMmmLagicZbFBMW3BVEtQVY1n2sZIBPLGimEFgjtezOrr8CB6tgxGLKxTacrSOzk4BXOo1pxuE96uE97ZoN/56c9lcvOnt+wf7B6967Uc/V43npvOV87XTcXznofPIeeYcOydO2Ljd6Dd+aPzY/L35R/Ov5t9X1MZO5fOlszKa//wHl+R44A==</latexit> ESD(n, ω, lat) = →K + 1 n2 n→1 i,j=0 K (ωb(i) → ωb(j))ω mod 1 = →K + 1 n2 nK(0) + b→logb n↑→1 k=1 #n(k)K ωb(k)ω #n (k) := card{k : ϕb (k) = ϕb (i) − ϕb (j) mod 1 s.t. i, j, ∈ {0,…, n − 1}} <latexit sha1_base64="mkuBHkUtpG4J1XZ1idhgNeKzDzo=">AAAGEnicjVRbb9MwFE7HCqPcNnjkJaIgbSiamrJuFQJpGpuGkNjKxi5sLpXjOK1VJw62061Y/hf8Gt4Qrzwj8W9w0lT0KmFVzun5vu/42OfYXkyJkJXKn8LCjcXizVtLt0t37t67/2B55eGpYAlH+AQxyvi5BwWmJMInkkiKz2OOYehRfOZ136T4WQ9zQVj0UfZj3AxhOyIBQVAaV2v5N/Bwm0QKUtKOnmsg8bUUgTo73jve1asHjg08Rn3RD81Hga9YQm18IZQdHioKpV6zSy/t1zYQSdhSkbFc/VkdaDuygSHm4bJg0f8EA18S6A90ikS2BmYjYdxRGQtBqg5NVms6Z9gsxjzbidAAR/5wG6XWcrmyXsmGPW24uVG28tForSw+BT5DSYgjiSgU4tKtxLKpIJcEUaxLIBE4hqgL21h1MO1haXwcR/gKsTCEZm0QwJDQvo8DmFCpFRDB0B5TX2dVMz6Dmqpl/1QX9yMm8T6Hfa2O9ne0qtec7KftZ3a5lo0SmCbPDLNDE5yHqTiuW3fc+uZs5hH2c6Jbd53qC6cym/cJU8qucmq1VnOq7pZTm0M+5DBqDxOoblRNChtZ4JFTgKFIG8HsLq2smMRS50wsNOdJuEll3Jv2kAiEkcSc9YiPhZ1pER/lXSYyqDdNY8WJxBEybIMFCbUls9PbYfuEYyRp3xgQcWJqb6MO5BBJc4fGVvQY60roCZPHaA8M2lVfuk2lwIyalF2tJyTcnyfJijND0Z+7yLBMM0SMzxMNy5WLdrG5ABy/N8d3mF0vwwQ9yLVKpzk4Yj2t0mkOHgqzQDrNwXlG4APGaNoNzjw9uP6epxqTu9q7/gfuTYI+CXLUvC/+JNo7N+DIg3Q+RbgYJ1xobd4Vd/IVmTZOq+vu5vrmh2p5+13+wixZj60n1qrlWlvWtvXWalgnFiq8KniFboEWvxW/F38Ufw6oC4Vc88gaG8VffwHhbCkf</latexit> WSESD(N, ω, lat) := N n=1 n ESD(n, ω, lat) in O(N) operations 14
15. of 23 Component-by-Component Search • Choose that minimizes from the pool - for lattices - random numbers in for Kronecker • For - Choose that minimizes • Cost of for ζ1 WSESD (N, ζ1 , { lattice Kronecker}) {1,3,…, ⌊N/2⌋} Nζ [0,1) ℓ = 2, 3, …, dmax ζℓ WSESD (N, (ζ1 , …, ζℓ ), { lattice Kronecker}) { 𝒪 (dN log(N)) 𝒪 (dN Nζ ) } { lattice Kronecker} 15
16. of 23 Comparing Discrepancies ˜ K (x) = d ∏ ℓ=1 [1 + γℓ (x2 ℓ − xℓ + 1/6)] 100 101 102 103 104 105 106 n 10°6 10°5 10°4 10°3 10°2 10°1 100 RMS Discrepancy Lattice d = 13, ∞ = (1.00, 0.25, 0.11, 0.06, 0.04, 0.03, . . . ) IID KCN CBC O(n°0.88) O(n°0.96) 100 101 102 103 104 105 106 n 10°6 10°5 10°4 10°3 10°2 10°1 100 RMS Discrepancy Kronecker d = 13, ∞ = (1.00, 0.25, 0.11, 0.06, 0.04, 0.03, . . . ) IID Richtmyer DGLPS CBC O(n°0.86) 16
17. of 23 ˜ K (x) = d ∏ ℓ=1 [1 + γℓ (x2 ℓ − xℓ + 1/6)] 17 100 101 102 103 104 105 106 n 10°6 10°5 10°4 10°3 10°2 10°1 100 RMS Discrepancy d = 13, ∞ = (1.00, 0.25, 0.11, 0.06, 0.04, 0.03, . . . ) IID CBC Kronecker CBC lattice O(n°0.87)
18. of 23 Keister Example ∫ ℝd cos(∥x∥)exp( −∥x∥2) dx 18 101 102 103 104 105 106 n 10°2 10°1 100 101 102 Keister Error d = 13, integral = -1.20491e+03 IID (19.6 s) Halton (322.9 s) Kronecker CBC (37.5 s) Lattice CBC (18.5 s)
19. of 23 Future work • Re fi ning the component-by-component search • Theoretical justi fi cation for component-by-component search • Stopping criterion for cubature - Not based on replications - E.g., based on tracking Fourier coe ffi cients [Jiménez Rugama and H 2016] or Gaussian process credible intervals [Jagadeeswaran and H 2019] • Quick computation of optimal non-uniform sample weights (Toeplitz matrices) • Optimizing digital sequences for all • Quality of sequences with missing data n 19
20. of 23 Speculation (w/o the shift) For What about a hybrid Welcome collaboration, discussion, and critiques! ℓ = 1,…, d Lattice: i ↦ (⋯000.i0 i1 i2 ⋯)b ∈[0,1) × (⋯ζℓ,2 ζℓ,1 ζℓ,0 .000)b ∈ℕ0 ⋯ mod 1 Kronecker: i ↦ (⋯i2 i1 i0 .000⋯)b ∈ℕ0 × (⋯000.ζℓ,1 ζℓ,2 ζℓ,3 ⋯)b ∈[0,1) mod1 i ↦ (⋯i2 i0 . i1 i3 ⋯)b ∈ℝ × (⋯ζℓ,1 ζℓ,0 . ζℓ,−1 ζℓ,−2 ⋯)b ∈ℝ mod1 20
21. of 23 Proposed Hybrid Points Courtesy of Dirk 21
22. of 23 References J. Dick, T. Goda, G. Larcher, F. Pillichshammer, and K. Suzuki. On the quasi- uniformity properties of quasi-Monte Carlo lattice point sets and sequences. arXiv:2502.06202. J. Dick, F. Kuo, and I. H. Sloan. “High dimensional integration — the Quasi- Monte Carlo way”. In: Acta Numer. 22 (2013), pp. 133–288. F. J. H, P. Kritzer, F. Y. Kuo, and D. Nuyens. “Weighted Compound Integration Rules with Higher Order Convergence for All N ”. In: Numer. Algorithms 59 (2012), pp. 161–183. F. J. H and H. Niederreiter. “The Existence of Good Extensible Rank-1 Lattices”. In: J. Complexity 19 (2003), pp. 286–300. R. Jagadeeswaran and F. J. H. “Fast Automatic Bayesian Cubature Using Lattice Sampling”. In: Stat. Comput. 29 (2019), pp. 1215–1229. 22
23. of 23 References Ll. A. Jiménez Rugama and F. J. H. “Adaptive Multidimensional Integration Based on Rank-1 Lattices”. In: Monte Carlo and Quasi-Monte Carlo Methods: MCQMC, Leuven, Belgium, April 2014. Ed. by R. Cools and D. Nuyens. Vol. 163. Springer Proceedings in Mathematics and Statistics. Springer-Verlag, Berlin, 2016, pp. 407–422. L. Matiukha, Y. Ding, and F. J. H. The Quality of Lattice Sequences. in preparation.2025+. D. Nuyens and R. Cools. “Fast component-by-component construction of rank-1 lattice rules with a non-prime number of points”. In: J. Complexity 22 (2006), pp. 4–28. R. D. Richtmyer. The Evaluation of De fi nite Integrals, and a Quasi-Monte-Carlo Method Based on the Properties of Algebraic Numbers. Tech. rep.LA-1342. Los Alamos Scienti fi c Laboratory, 1951. 23