HDA_2025

Slides from a talk in Bonn at High Dimensional Approximation 2025, given September 12

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 Matiuika, 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 3
4. of 23 Motivation • Extensible lattice and digital sequences have preferred sample sizes of n = 1, b, b2, … 3
5. of 23 Motivation • Extensible lattice and digital sequences have preferred sample sizes of n = 1, b, b2, … • IID samples have no preferred sample sizes 3
6. of 23 Motivation • Extensible lattice and digital sequences have preferred sample sizes of n = 1, b, b2, … • 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? n = 1, 2, 3,… d = 1, 2, 3,… 3
7. of 23 Motivation • Extensible lattice and digital sequences have preferred sample sizes of n = 1, b, b2, … • 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? n = 1, 2, 3,… d = 1, 2, 3,… • Why? - Run out of time - Missing data 3
8. 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
9. 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, 91
10. of 23 What we know 6
11. of 23 What we know • Any nodes for integration for , using equal sample weights do no better than error [H, Kritzer, Kuo, Nuyens 2012] n = 1, 2, 3,… 𝒪 (n−1) 6
12. of 23 What we know • Any nodes for integration for , using equal sample weights do no better than error [H, Kritzer, Kuo, Nuyens 2012] n = 1, 2, 3,… 𝒪 (n−1) • Good lattice by component-by-component (CBC) constructions for and [Nuyens & Cools, 2006], [Dick, Kuo, Sloan 2013] ζ d = 1, 2, … n = 1, b, b2, … 6
13. of 23 What we know • Any nodes for integration for , using equal sample weights do no better than error [H, Kritzer, Kuo, Nuyens 2012] n = 1, 2, 3,… 𝒪 (n−1) • Good lattice by component-by-component (CBC) constructions for and [Nuyens & Cools, 2006], [Dick, Kuo, Sloan 2013] ζ d = 1, 2, … n = 1, b, b2, … • Kronecker - [Richtmyer 1951] - [Dick, Goda, Larcher, Pillichahammer, Suzuki 2025] ζ ( 2, 3, 5, …) mod 1 (21/(d+1), …,2d/(d+1)) mod 1 6
14. 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
15. 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
16. 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
17. 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
18. 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
19. 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="5iJP7mt1p+ZYhw80YG8Gp+BGqlg=">AAAIMnicjVVNb9s2GFbjbu68r2Y77kLMW5FuaiBpdWoMKFB0CTqsGJoVS5vWdAxKomw21EdJyrFB8LLr9nP2Z7bbsOuuu++VorSWIgUjDJni8zzvB1/ylZ9xJpXj/HFtq3f9nXf7N94bvP/Bhx99fHP7k2cyzUVAj4KUp+LYJ5JyltAjxRSnx5mgJPY5fe6fflfgz5dUSJYmP6t1RqcxmScsYgFRsDTb3voX+3TOEk04mydfmQGOiVr4vj4wCPtszif7J94O1thPeSjXMfzplZkx9DXaXML7lCtSSOI0rCGuwWam2X3HnOjkjmvsx7dLw2KKBrfQfTTosN9Q4TMW0gVR+rEBPS6ldxDCLFEzPXFsd3oCfhWLqUTVK0TzVrSz6UAZG9Udgk1YKlIXsS6UNTbqglam2IdIkADy1MmJB7DMY4jcfvUm9s4wyjybkcxeoY0EcQrFK2oL2sH/daUYD2mrs8Ji01tbyepBOedbjhVdKX22oIIiOCdXeLp9C30L4XfnbTfMg7/Xr3MS1vI9t7FZ4Kvzu6qGKwiYJuGbUz67OXR2nXKgyxO3mgytahzOtq9/gcM0yGOaqIATKSeuk6mpJkKxgFMwn0uakeCUzKleUL6kCtYETehZkMYxAd84IjHj65BGJOfKaCyji3lNvSpvNawBCjtRvulTuk5SRR8Jsjb66aOHRo9Hdvkz6Es0HJVjgC+TW8085DmtzMDOumPbHe+1M5/SsCK6Y9f2vrGddt4Lynl6VlG90cj23Hv2qIP8RJBkfhGAd9eDEO6Whjd2gcSyqB1kV1RUNrFisRWLYT+ZgFDqq8WpkJEESSbSJRwiiUptIDZ5k1xF46lmSZYrmgTABizKOVIpKronCpmggeJrmJBAMKg9ChYELqWCHlvz6KfpqSK+hDg2zwD05ThbmIk71Rq31GToGtOQiLBLUhanRbHudHJRphZRKrpEF+WqRPsULoCgP8L2PcmoIAqYeEmE0cWjAw/SpdHFowOPJTgoHh24KAninLEZ9qFIfbhL1VfrsJnVweoteNAEQxZVaNkxGujy2NQ+S8eXCC/rhJfGQF9xm13k8uSZt+vu7e795A0f/FB1mBvWZ9bn1o7lWvesB9b31qF1ZAU93Pul92vvt/7v/T/7f/X/PqduXas0n1q10f/nPy8c7/4=</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, 0) where K(x) := K(x, 0), K := [0,1]d K(x) dx 12
20. 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
21. 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
22. 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
23. 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
24. 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)
25. of 23 Keister Example ∫ ℝd cos(∥x∥)exp( −∥x∥2) dx 18 101 102 103 104 105 106 n 10°3 10°2 10°1 100 101 102 Keister Error d = 13, integral = -1.20491e+03 IID – (20.4 s) Halton – (323.1 s) Kronecker CBC – (38.3 s) Lattice CBC – (19.9 s)
26. 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. tracking Fourier coe ff i 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
27. of 23 Speculation (w/o the shift) For What about 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
28. of 23 Proposed Hybrid Points Courtesy of Dirk 21
29. 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
30. 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