Share
Embed
Unified Tractability MCM 2025
Talk given at Illinois Institute of Technology for MCM 2025
Fred J. Hickernell
July 24, 2025
Transcript
14 slides
-
Fred J. Hickernell, Illinois Institute of Technology Monte Carlo Methods,
July 29, 2025 A Unified Treatment of Tractability for Approximation Problems Defined on Hilbert Spaces • Joint work with Yuhan Ding, Onyekachi Emenike, Peter Kritzer, and Simon Mak • Thanks to US National Science Foundation #2316011 Slides at speakerdeck.com/fjhickernell/uni fi ed-tractability-mcm-2025 -
of 14 • Tractability = how much function data required
to solve a sequence of numerical problems as - error tolerance, , vanishes and - dimension, , tends to in fi nity • Cones = sets of input functions are not balls, but closed under scalar multiplication You must make assumptions to make rigorous arguments ε d Two thoughts 2 -
of 14 <latexit sha1_base64="9FX0ehDDPF0Shl+gA8g1tzqMOFM=">AAADHnicbVJdb9MwFHXC1yhfHTzygMU0CYmqSvZQKiSkMaSNByS2QreJpqoc52a16sTBvoFVVv4L/wD+BIgXxCv8G9xkD3TtlSwd3+tzr32O40IKg0Hw1/OvXL12/cbGzdat23fu3mtv3j82qtQchlxJpU9jZkCKHIYoUMJpoYFlsYSTePZqUT/5BNoIlb/HeQHjjJ3lIhWcoUtN2t+jMk9Ax5pxsFHGcKoz++7tm2qSVBMbIZyjSa2N6kl2BvNcIezJEiq7GMl0VVFVgGaoHHxOV9oZru3+cjeRFyUaR4xQrSccLBNUiQ2jQ6OPJUtoQl/QsEN33F4mCs2kvRV0gzroKggvwNZuvB8/+vrz2+Fk03sZJYqXGeTIJTNmFAYFji3TKLiEqhWVBgrGZ+wMRg7mLAMztrUKFd12mYSmSruVI62z/zMsy4yZZ7E7Wb/ocm2RXFcblZj2x40+kPNmUFpK6nRamEcToYGjnDvAuBburpRPmdMOncVLU86bq7aiBFLn0xr7Bgd7lQ06YdjvhP1eRek2HUAhnQ/0s8ApnbsvtuZp9RcxqalaTvTwssSr4HinG/a6vSOn/oA0sUEeksfkCQnJM7JLXpNDMiTce+odeR+8kf/F/+H/8n83R33vgvOALIX/5x9fDAin</latexit> SOLd linear operator : Fd inputs
→ Gd outputs , d = 1, 2, . . . {ui,d }∞ i=1 {vi,d }∞ i=1 is an orthonormal basis for ℱd 𝒢 d <latexit sha1_base64="ryZf7FVixIl/Q5IlMLfZoIrmVk0=">AAAC7XicbVJdb9MwFHUCgxG+OnjkxaKaNERVJRV0vCCN8bKHIQas26Q6qlz7prPqxCF2qlZWfgZvCB75TfwbnCYaY+VKto/O8bWvz/U0l0KbMPzt+bdub925u30vuP/g4aPHnZ0nZ1qVBYMRU1IVF1OqQYoMRkYYCRd5ATSdSjifzt/X+vkCCi1UdmpWOcQpnWUiEYwaR006P8mYpNRcFqn98vG4mnC8V06s6PHqBX6LiXQncdoQeNGsPUy+lpQHV2JUi2QGf7cPrhjGldG4ycDEwNLoxJJ13XYOq0wZOJQlVFpksz7BCyrdzIGpNO9XJA4mnW7YD9eBN0HUgi5q42Sy4w0JV6xMITNMUq3HUZib2NLCCCahCnZJqSGnbE5nMHYwoyno2K5LqvCuYzhOVOFGZvCaDa5nLKNondHDfCFy3WK9mLXIUGd9bJfNeQHhkLjWbD7YHp1+OK5sGO4PD99V16+wNNV6lU5dMXVn9E2tJv+njUuTvImtyPLSQMaatySlxEbhuvWYiwKYkSsHKCuE8wOzS1pQZtwHqZ2Obvq6Cc4G/WjYH34adA8+t55vo2foOdpDEdpHB+gInaARYt6W99J75b32lf/N/+7/aLb6XpvzFP0T/q8/nUPp6Q==</latexit> SOLd(ui,d) = ωi,dvi,d, ω1,d → ω2,d → · · · sing. val. decomp. <latexit sha1_base64="T/ICfbj5QCbln5JSj8ufOXASCYE=">AAADPHicfVJNaxNBGN5dv2r8aKpHL4Oh0MISsj3EXAqxQhURjNG0hUxcJrPvJkNmZ9eZWdt1mL/m//Dem3j17GQTwTbFFwYenvf7eWdacKZ0p/PDD27dvnP33tb9xoOHjx5vN3eenKi8lBRGNOe5PJsSBZwJGGmmOZwVEkg25XA6Xbxa+k+/glQsF590VcAkIzPBUkaJdlTcvMRjnBE9l5l5ORjYONlLQ7GPDhFWZRYbdhjZzwL9Dfn4/t0ypHSOMLH7CIcIlyIBOZWEgsGciBkHlIZoHYJlzcSmrqCoNMeugLWO0HChVWpwvYNZQCVyDUe8BMsSIBxZfO7AnGiT2lUx28BfSpKg/6SmTDAN6NjJw0Ait4PFk0bcbHXandrQJojWoOWtbRDv+H2c5LTMQGjKiVLjqFPoiSFSM8rBDVIqKAhdkBmMHRQkAzUx9TwW7TomQWku3RMa1ey/GYZkSlXZ1EXWqlz3LcmbfONSp72JYaIoNQi6apSWHOkcLW+LEiaBal45QKhkblZE58SdRrsfcKXLxWrUBk7ASQabQprh6yNrOmEU9cKo17UI7aIhFNydGZ0zPUeVk/iG1eqPolJlnebRdYU3wclBO+q2ux8OWv3hWv0t75n33NvzIu+F1/feeANv5FH/rV/4lf8t+B5cBj+DX6vQwF/nPPWuWPD7DzH0Dzc=</latexit> APPd(f, n) = n i=1 SOLd(ui,d) →f, ui,d ↑Fd ideal fi,d finite Fourier sum Sequence of Ideal Linear Problems on Hilbert Spaces 3 -
of 14 4 easier problem for smoother inputs (larger )
<latexit sha1_base64="dPOX9f6sCEGr/CiaT5YeVi7RJGM=">AAAGVHic3ZTPb9MwFMezrS2j/NrgyOWJaWhDY0p62LggjSHBJAYM2C9p7ioncVKrjpPGztTK8hX+QyT+C/4ADryk3Wi3aTc44EP9aue99/XH79nPBFfadX/MzM7V6o1b87ebd+7eu/9gYfHhoUqLPGAHQSrS/Ninigku2YHmWrDjLGc08QU78nuvy/2jM5Yrnsp9PcxYO6Gx5BEPqMalzuLcT+KzmEtDBY/lM9skCdVdFeTmje2E8BSIZgOdJwa6VAFm4gosEJ/HsQBi0EpFqIYJTmZg0TlTOgWS5WnYMYQJ/IhLqIJGOe2ZwlowpNJtemwoU822RcEsiWmS0E7l0aumU/OcUJF1KXoQ1c+1aaERM4lxAkOMNcRa40KmrfFsGVPhr+LSwgq0UAIfB4JBNa2SNSDbPAaCPDSU/ya09yzKnVJ5odv3zQd7Or2LzlOHQoWFr5hmfYTi4a4IU63WICQWRrTyyiJ/+L79a3z/D1rnrJDNl4+7CGslWkVeLyEC0u8XNByhU9F15RQVMigLHGiGqAY8qcod0hxyFqR4pGEV3xCBrRLSjuFroSV4Ko4JvFI/l5Ee2irhxG3czP2GGv7nHM8xNgmT4UV34+gsLLnrbjXgquGNjSVnPPY6izPvSJgGRcKkDgRV6sRzM902NNc8EMw2l0mhWEaDHo3ZCZqSJky1TXUrFpZxJYQI0Uep1FCtNic9Bp5XeaDuM56psa3O4rGlKT5mbTMYxWuSkEX42F29c7Oz/34Xa9zd3Nh+ZSdTGJqokjiKqbrv8l65eN3eSaGjF23DZVZoJoPRWaJCALZg+ZhCyLGctBiiQYOcIw8IuhQ7TuOTO5WlqmQVKYv4vcuwrxqHrXVvY33jU2tp6/P4Iuadx84TZ8XxnE1ny9lx9pwDJ6gd1Wzta+1b/Xv9V2OuUR99Ojsz9nnkTI3G/d/obTRt</latexit> Fd has basis x →↑ ω→u ωωk↑ε ω ↓ 2 cos sin (2εkωxω) ku ↔ Nu, u ↗ {1, . . . , d} Gd has basis x →↑ ω→u ↓ 2 cos sin (2εkωxω) ku ↔ Nu, u ↗ {1, . . . , d} SOLd(f) = f function approximation or recovery {ϑi,d }↓ i=1 = ω→u ωωk↑ε ω | ku ↔ Nu, u ↗ {1, . . . , d} α Ex. Periodic Functions on the Unit Cube -
of 14 5 How does increase as and ? <latexit
sha1_base64="YiQEFuPk1gE35+wQMG0dkBcdQaw=">AAAEunicfVNNTxRBEB3WVXH9Aj16qUhIQFeywwEJkQQxAQ8GV5SPhMFJz0zNbmd7esbuHmDT6f/nX/BPeNWjNbOLsrCxT5Wq6lfvva6OCsG16XR+zDRuNW/fuTt7r3X/wcNHj+fmnxzqvFQxHsS5yNVxxDQKLvHAcCPwuFDIskjgUTR4V9WPzlBpnssvZljgacZ6kqc8ZoZS4XyDBRH2uLQ9ZvqoXrhWkFGkMvu223VhspS25TJsbEKgyyy0fNN3XyVc9nz++KHqKanQTtwyBG0ISpmgihSL0QaCyZ5ASNswbglUnQltjaBjZXcIwDlKnPME+8zY1I1aHQTfSpZAYPDC6LRlg1qtHeBQ5ga3RYku5ZIbhB1yg6MCoki3glYgDlGZ6yzTZXgFN9Tt0egzprDQXOSy/ZfXdsWLFKkK6grf3SoPAam6co2ojrimuWJCQAoBl5NWTOCG08TYsVJbkiiICMc5V6kZpwkbHEyg/pf89CmXaFwSXlZvAcR5Vgi84GZIrtNTZxV5K0ciKswosnsu7MAGCafdSlho5Uu/Pc0IWiCUyb91arXCuYXOSqc+cDPwx8GCNz7dcH5mK0jyuMxQmlgwrU/8TmFOLVOGxwJpQqmxYPGA9fCEQsky1Ke21upgkTIJVGaluTRQZ6/esCzTephF1Fnbdb1WJafVTkqTrp+Sb0VpUMajQWkpwORQ/SxIuMLYiCEFLFacuELcZ/ROhv7fxJSLEdVWkCBtME5Zhf3dbWc7bd9fb/vra/Tqi7CPhaA3h3Nu+jCkjZ8irV5unWpHnvvXHb4ZHK6u+Gsra59WF7b2x+7Pes+8596S53uvvS3vvdf1Dry48b3xs/Gr8bv5phk1eXMwam3MjO889SZO0/wBy82eQA==</latexit> APPd(f, n) := n i=1 SOLd(ui,d) →f, ui,d ↑Fd fi,d finite Fourier sum ↓SOLd(f) ↔ APPd(f, Nω,Bd )↓Gd ↗ ω ↘f ≃ Bd unit ball for Nω,Bd information complexity = min{n ≃ N 0 : εn+1,d ↗ ω} Nε,ℬd ε → 0 d → ∞ Information Complexity [Novak & Woźniakowski 2008] -
of 14 6 Condition on minimum of ordered singular values
becomes a summation condition involving singular values <latexit sha1_base64="K4ezDoe9XLW6sw28GcdziATUUzk=">AAAD+3ichVPbbtMwGE5bDiMctsElNxZlCEFXJbvYEAJpdDeTGNOQdpLmLnKcP621xAmxU7Wy/Bw8AHeIWx6Gl0H8ScPUbUhYsvL5P37/IWGeCKU971er3bl1+87dpXvu/QcPHy2vrD4+VllZcDjiWZIVpyFTkAgJR1roBE7zAlgaJnASXuxU+pMJFEpk8lDPchimbCRFLDjTKApWW19pCCMhDUvESL6ytJQRFGHBOJj9wNAJKyBXIslkj6ZMjxUvzMAGkbWorNObC5jJTMMgKcFSDVOtYiNknBVpn/AszfvWkhfkPaGpkIQavNW3ChaGZt8GHnlLaIKUIxYY+drvRRbfQBZyE9qIFtjtBCZHaW/R7tys5/9hJjNiSZWBupdk4xjfX0oWIU8KU+y6Invz8I0JUSUfEz1mGr1dqso8MNG1QtBalWlgBNZae9tzNIj1jNAYGRvfmssyBRY5J0vekbmVS0FGf8fgusFK1+t79SE3gd+ArtOcAxzlRxplvExBap4wpc58L9dDwwoteALWXaOlgpzxCzaCM4SSpaCGpm6VJWsoiQhODa/UpJa6ix5T3689eiSaiFw1WE1GDdIMd25opvN4Lo0gxp28OQize/hpzxrP29ocfLCLKQxLlZqlIZKpV+26rhL+S3dW6vjNEHcuLzVIPq8lLhOiM1LtPIlEAVwnMwSMFwL7QfiY4Uw0/hlXslSxCxUri+33rzf7Jjje6Pub/c3PG93t/WYQS85T55nz0vGdLWfb2XUOnCOHt363n7fX2/2O7XzrfO/8mJu2W43PE+fK6fz8A6k6VBs=</latexit> Nω,Bd inform. comp. = min{n → N 0 : ωn+1,d ↑ ε} ↑ Cp ε→p no d i! ↓Lp such that sup d↑N ↓ i=Lp 1 ω→p i,d < ↔ Algebraic Strong Polynomial Tractability -
of 14 7 <latexit sha1_base64="IJFqxXNbwYVRzXX54c9yutgbzsA=">AAAIUXic3ZXPc9w0FMedtN1sXX40cOTyppl2EghhvYe0B8K06Qx0hlIKJG1noq1HtmVHs7LsWHJmtxqd4D/kxB/BH8CNZ9lZvJuQE3DAh/VbSe/p+z5+eopKwZUejX5bW79x89ZgY3jbv/Pe+x98eHfzo1eqqKuYHceFKKo3EVVMcMmONdeCvSkrRvNIsNfR9Gkz//qcVYoX8kjPSzbJaSZ5ymOqcSjcvPU7iVjGpaGCZ/JT65Oc6lMVV+ZrGybwAIhmM13lBk6pAtyJK7BAIp5lAohBqxCJmuf4MjOLzqXSBZCyKpLQECZwEZfggqYVnZraWjDE6TZTNpeFZoeiZpZkNM9p6Dym7vXWfE6oKE8pehB1VmkzRiNjEuPEhhhriLVmBKW2JrBNTIW/iksL2zBGCbwLBDP32iG7QA55BgR5aGj+9bRPLcpdUrnQHUXmhX27PIvOS0mhwjpSTLMzhBLgrEgKrXYhIRZaWpWzyF98v/nX+P4/aF2wQjY/ff8cYW2nO8jrAFIgZ2c1TVp0Kr2qnNJaxk2BAy0R1YznrtyhqKBicYEpzV18QwQelYSGhu8mlmBWHDcIGv1cpnpu3Ya9r3E992tq+D/nuCi6Jk9Vl6FJVoI793yRcpsxEFcwTYn00WAiJTr4DsffRVuFsyJpUdYnEMBnMO5wOQfbSpke9NlPm10X/Fw+MAH/n1NwTSPqVL1jmm53GnZ6IhDqA/gSLpjxNL2yq5XwFQRftO6LcgUqE7iA32xz0KPfK6GL8L4L/wLXntOKlYqLQu7Coo8c4tHAaILB07CE3pr2m/mEyWTR3cO7W6O9kXvgshF0xpbXPS/DzbVvSVLEdc6kjgVV6iQYlXpiaKV5LJj175NasZLGU5qxEzQlzZmaGMfCwn0cSSDFc5cWUoMb9fsesyBwHvh9znmpOludZ52lKd5kEzNr4/kkYSnedJdJm2dH3z3HBjd6uH/4xPa3MDRXzXFDMQ7Z6lwzeNXcSa3TRxPDZVlrJuM2l7QWgP23uUkh4dhLtJijQeOKIw+ITymeHo337dIuro2pVFnEH6zCvmy8Gu8F+3v7P4y3Hv/YfYih94l3z9v2Au+h99h75r30jr14cDR4N/h58MvGrxt/DL3hert0fa3z+dhbeoZ3/gT0Xu0k</latexit> Fd has basis x →↑
ω→u ωωk↑ε ω ↓ 2 cos sin (2εkωxω) ku ↔ Nu, u ↗ {1, . . . , d} Gd has basis x →↑ ω→u ↓ 2 cos sin (2εkωxω) ku ↔ Nu, u ↗ {1, . . . , d} SOLd(f) = f function approximation or recovery {ϑi,d }↓ i=1 = ω→u ωωk↑ε ω | ku ↔ Nu, u ↗ {1, . . . , d} sup d→N ↓ i=1 1 ϑ↑p i,d = sup d→N ω→{1,...,d} 1 + 2ωω ↓ k=1 k↑pε = sup d→N ω→{1,...,d} 1 + 2ωωϖ(pϱ) < ↘ ≃⇐ p > 1/ϱ and ↓ ω=1 ωω < ↘ ≃⇐ Nϑ,Bd ⇒ Cpς↑p Strong Tractability for Approximation of Periodic Functions -
of 14 8 <latexit sha1_base64="nYnHgduDmdoWQ8FseLkTRQLfKWU=">AAADzHicbVJbb9MwFE5bLiPcNsYbL0dMQwhKleyhQwiksb3sYVRD2k2a28hxTlprjpPFTtXK8iv/kXd+CE6bTWXDkuXP536+c+JCcKWD4Her3Xnw8NHjtSf+02fPX7xc33h1pvKqZHjKcpGXFzFVKLjEU821wIuiRJrFAs/jq4Nafz7FUvFcnuh5gcOMjiVPOaPaiaKNliUxjrk0VPCx/GBJJRMs45IyNIPIkCktsVBc5LKbWOsEi5TmCucy17gvKrRE40yr1HCZ5mXWA5ZnRc9aeAffgGRcAjHu1m9G9SSOzcBGAXwBIlyZCY2M/Bi64O6PsJIPyFJ0EJmie+1wd1U7Mp8KC8nI1Bri39aQpu5/XdHEpSc4cwQqOLqJ0BiBqtgE9IRqsOATVRWRSe5U6KxVlUWG100IhlzchklG10DKWmRHzinVcyCpI8yE1tz2xF1HKzVa+ApLW5+gTG7Y9qP1raAXLA7cB2EDtrzmHLuB9UmSsypDqZmgSl2GQaGHhpaaM4HW3yaVwoKyKzrGSwclzVANzWJsFradJAE3J3elhoXUX/WYheHCowvJlBeqwWo6bpCmbrOGZraM55MEU7d595fCHJ78OLImCHb7+9/tagpDM6XmWeyKqdlWd3W18H+6y0qnn4duy4pKo2TLXtJKgM6h3mxIeIlMi7kDlJXc8QFsQt1gtNv/munwLq/3wdlOL+z3+j93tvYGDedr3hvvrffeC71db8879I69U4+1/rT99mb7dWfQ0R3TsUvTdqvx2fT+OZ1ffwH5HD1w</latexit> Nω,d inform. comp. = min{n
→ N 0 : ωn+1,d ↑ ε} ↑ Cp,q ε→pdq i! ↓Lp,q such that sup d↑N ↓ i=↔Lp,qdq↗ 1 ω→p i,d dq < ↔ Algebraic Polynomial Tractability -
of 14 9 Includes algebraic/exponential (strong) (quasi-)polynomial tractability <latexit sha1_base64="w4gBcQDMszWwBiq2XbgF94CqfE0=">AAAEvHicdVRfb9MwEM9KgRH+bfDIy4lpqBulaoY0JgRo2h7gAU1j6v5I84gcx2mtOk6InbHK8hfkG/AteIUnLmkZXddZSXw+n+9+9/NdolwKbbrdnwuNW83bd+4u3vPvP3j46PHS8pMjnZUF44csk1lxElHNpVD80Agj+UlecJpGkh9Hw91q//icF1pkqmdGOT9LaV+JRDBqUBUuNxiJeF8oS6Xoq3U3veKx80mpYl5EBWXc7oWWnNOC51rITLVj51BRQ7BDPlKZ4Tuy5I4YfmF0YoVKsiLtAMvSvOMcvID3QFKhgFh8qzmlZhBFds+FXXgLRCLsmIZWvQzQOa45TMUDMlbtYtAok7EepTjZHD2TNvRIJPqyNWX/1b4KXJv0uUoQvSXWWeKc7ebG2aB+YteGq66g8lKsEeLXSRSpFUmC2m8ljRE/EH6BV6Lh8xwMkwPwXZgBOPCJLvPQxjOZoqEu09CKigzJE4NfxoWc57JXG7S6NyTx+l8SszkUoj8wa5MZp8q/+4o4EjMCUjvCg73WJeEC6R7TBfNDbdzA15qDdzB27BOu4su6+b9Yd74fLq10O916wHUhmAgr3mTsh8sL2yTOWJlyZZikWp8GiOPM0sIIJnlVlprnlA1pn5+iqGjK9Zmta9HBKmpiwOLDVxmotdMnLE11lQJaVveiZ/cq5by909IkW2dY13lpuGLjQEkpwWRQ9RbEouDMyBEKlBUCsQIbUGTTYAdeiXIxhuqTmCfYudebyB583EHy20Gw1Q62Nh3AKhzwXGIfjitshH+AOalVoAudaIecB7MMXxeONjrBZmfzy8bK9sGE/UXvmffca3mB98bb9j55+96hxxo/Gr8avxt/mh+acXPYTMemjYXJmafeldE8/wsbUZ6X</latexit>
Nω,d inform. comp. = min{n → N 0 : ωn+1,d ↑ ε} ↑ Cp T ε→1, 1 d , p i! ↓Lp with sup d↑N ↓ i=↔LpT (0,{1 d },p)↗ 1 T(ω→1 i,d , {1 d }, p) < ↘ Unified Tractability [Emineke, H, and Kritzer 2024] -
of 14 10 <latexit sha1_base64="YU0yh1yvErZ3vytMNkdUQZJNr2I=">AAAGMnichVRNb9w2EJWT3TbdfiROj7kMYizgpGtjtQfXCBrASYCkhyJ13doJYNoCRVFrrilKJinHC4L/qn8muRW99kd0KCnerr1AeZBGnCHnzZs3SispjB2PP67dudvrf/Hlva8GX3/z7Xf3H6w/PDJlrRk/ZKUs9fuUGi6F4odWWMnfV5rTIpX8XXr+KvjfXXJtRKn+sPOKnxR0qkQuGLW4lazf/UhSPhXKTak94/qpH6hkDD+BSuLmOcEnYVlpzQjIxUVNMyBGTAuazDbzJ/AMngNJxVQCkUdcW9gkEpNnNHFilHkgH0TGz6h1uW93nuDruUrcbCv2P8T+1Klk5psrNBAdrkjcxBMyIAUCMky7Vz7JFnmIgxyIUHDtfx38BNFdhvzBaPG5mQ8IieQYKzBl3NgaC8KMFNJTvQjd0tcgPKZypGHWnfO5Ki1/KWvuHbH8yprcsVJxKHNQgnHIa8UCk8Z7RA2DYYNLF+7F/j4C28xHCllC8KYuQulYcocdY37/9ZcQU3fUNOBrlXGdasq4QyrVFCHnI+hCiG52kMtbxCL+tjstysFwVQ25UMJyeI3qEVwDYsJjyHXbuxuwkLwtuFXOW8x9STWvjJClGi21aZSHIrouXnveoMe3fVgcvBZTXmoq5c2mhtsCsI5yDAIPS+T8D45AkalTYyk7X8XEoplFVdtmGKgEVhobGIEVJ4DQqtLl1WeGHQiFuIptAuESya+EnaMKUD5B36dP/ahryQA/Gg0UoURUWRgXN1tUnKburUeNf56slqwc63RLlJkLbVHGW6jdifeOpq1oG9UOCFfZYopxJQ82xtvjZsFtI+6Mjahb+8n62h7JSlYXXFkmqTHH8biyJ45qKxiqbkBqwysklE75MZqKFtycuIYqD0PcySB0Ki+VhWb3vyccLYyZF4h52PTqpi9srvId1zbfPXFCYZ+4Ym2ivJZgSwh/NMiE5szKORqUaYFYgZ1RJM/if28py1ULdUAyjpPAV8z4wZuX3o1Hcbw7ind3UHJDOOCVRMHBB2HPYI6Ts6K0ZkhMbjxyHt9k+LZxNNmOd7Z3fpts7B107N+LHkWPo80ojn6M9qKfo/3oMGK9vV7eK3tV/8/+p/5f/b/b0Dtr3Znvo6XV/+dfPPIfoQ==</latexit> n0 < n1 < n2
< · · · , ωj(f) := (εi,dfi,d) nj i=nj→1+1 2 Cd := f → Fd | ωj(f) ↑ min 1→r<j abrωj↑r = cone of nice functions ↓SOLd(f) ↔ APPd(f, Nω,Cd,f )↓Gd ↑ ϑ ↗f → Cd for Nω,Cd,f computational cost ↓ inform. complexity = nj↑ , j↔ := min j → N : ωj ↑ ϑ ↘ 1 ↔ b2 ab Infer Bound on from Data [Ding, H, & Jiménez Rugama 2020] ∥f∥ℱd -
of 14 11 <latexit sha1_base64="UHradqT/9bfE5hIq6q9yhLGqUek=">AAADv3icbVNbb9MwFE5XLqPcNnjk5Yhp0sa6qqnQmBCTxiYBT2hM7CLNXeQ4J607x8lsZ1tl+SfyA/gdvIKEk1aUXY4U5dO5+Pv85SQuBNem2/3ZmGveu//g4fyj1uMnT589X1h8cajzUjE8YLnI1XFMNQou8cBwI/C4UEizWOBRfLZb1Y8uUGmey+9mXGA/owPJU86o8alosZGSGAdc2gE1Q1RvXEtGI9iC3qkdrb11bRgB4RJI5stxbL+6qNsGcn5e0gSI5oOMRqOVdBXe+xkS84EAIg5RGVghwqtIaGR5O3FALnmCQ2ps6iaZVf/akpEdrYduLXSn1vO6+ggFRFVHRLbnCGnV1Jopu+uiZMZDLKQzaVX9U1UnXt1FxV+BiT47cpVCItD3ck8Z1ljBB/CM/qLryguYda+rfzqcZ7Okdtme4VjmBndEic4Sg1dGp5blEiFPQXKGkJaSVa5q51yLoExmpraihaVup1sH3AbhFCwF09jzX2abJDkrM5SGCar1SdgtTN9SZTgT6AlKjQVlZ3SAJx5KmqHu21qrg2WfSSDNlX+kgTr7/4SlmdbjLPadtX03a1XyrtpJadLNvuWyKA1KNiFKSwEmh2q9IOEKmRFjDyhT3GsFNqSKMuOX8BrL1URqiySY+uW9w+T9zzvOdtthuNkONzccwDLsYyGot/qSmyGM/U9wx9Uq0Uqn2nnPw5sO3waHvU640dn41lva3p+6Px+8Cl4HK0EYvAu2gy/BXnAQsMaPxq/G78af5sfmoCmbxaR1rjGdeRlci+b4L/gINXE=</latexit> nj = 2j+4, j →
N 0, ωj(f) := (εi,dfi,d)nj i=nj→1+1 2 Cd := f → Fd | ωj(f) ↑ min 1→r<j 2↑r+1ωj↑r = cone of nice functions Ex. Nice Periodic Function in Cone 0.0 0.2 0.4 0.6 0.8 1.0 x °0.2 0.0 0.2 0.4 0.6 f(x) 2 8 32 128 512 2048 8192 i 10°12 10°10 10°8 10°6 10°4 10°2 100 b f(i) n0 n1 n2 n3 n4 n5 n6 n7 n8 n9 16 32 64 128 256 512 1024 2048 4096 8192 j 10°10 10°8 10°6 10°4 10°2 æj (f) n0 n1 n2 n3 n4 n5 n6 n7 n8 n9 upper bound -
of 14 12 <latexit sha1_base64="UHradqT/9bfE5hIq6q9yhLGqUek=">AAADv3icbVNbb9MwFE5XLqPcNnjk5Yhp0sa6qqnQmBCTxiYBT2hM7CLNXeQ4J607x8lsZ1tl+SfyA/gdvIKEk1aUXY4U5dO5+Pv85SQuBNem2/3ZmGveu//g4fyj1uMnT589X1h8cajzUjE8YLnI1XFMNQou8cBwI/C4UEizWOBRfLZb1Y8uUGmey+9mXGA/owPJU86o8alosZGSGAdc2gE1Q1RvXEtGI9iC3qkdrb11bRgB4RJI5stxbL+6qNsGcn5e0gSI5oOMRqOVdBXe+xkS84EAIg5RGVghwqtIaGR5O3FALnmCQ2ps6iaZVf/akpEdrYduLXSn1vO6+ggFRFVHRLbnCGnV1Jopu+uiZMZDLKQzaVX9U1UnXt1FxV+BiT47cpVCItD3ck8Z1ljBB/CM/qLryguYda+rfzqcZ7Okdtme4VjmBndEic4Sg1dGp5blEiFPQXKGkJaSVa5q51yLoExmpraihaVup1sH3AbhFCwF09jzX2abJDkrM5SGCar1SdgtTN9SZTgT6AlKjQVlZ3SAJx5KmqHu21qrg2WfSSDNlX+kgTr7/4SlmdbjLPadtX03a1XyrtpJadLNvuWyKA1KNiFKSwEmh2q9IOEKmRFjDyhT3GsFNqSKMuOX8BrL1URqiySY+uW9w+T9zzvOdtthuNkONzccwDLsYyGot/qSmyGM/U9wx9Uq0Uqn2nnPw5sO3waHvU640dn41lva3p+6Px+8Cl4HK0EYvAu2gy/BXnAQsMaPxq/G78af5sfmoCmbxaR1rjGdeRlci+b4L/gINXE=</latexit> nj = 2j+4, j →
N 0, ωj(f) := (εi,dfi,d)nj i=nj→1+1 2 Cd := f → Fd | ωj(f) ↑ min 1→r<j 2↑r+1ωj↑r = cone of nice functions Ex. Nasty Periodic Function Outside Cone 16 32 64 128 256 512 1024 2048 4096 8192 j 10°10 10°8 10°6 10°4 10°2 æj (ffuzzy ) n0 n1 n2 n3 n4 n5 n6 n7 n8 n9 2 8 32 128 512 2048 8192 i 10°12 10°10 10°8 10°6 10°4 10°2 100 b ffuzzy (i) n0 n1 n2 n3 n4 n5 n6 n7 n8 n9 0.0 0.2 0.4 0.6 0.8 1.0 x °0.2 0.0 0.2 0.4 0.6 ffuzzy (x) -
of 14 13 • Do the uni fi ed tractability
arguments for extend to ? • What else can be done on cones of inputs? • Banach spaces [Ding, H, Kritzer, and Mak 2020] • Optimality of homogeneous algorithms [Krieg, Kritzer 2024] • Can unify the tractability conditions for the real world of function values? [Novak & Woźniakowski 2012] ℬd 𝒞 d Outstanding Questions -
of 14 References Ding, Y., Hickernell, F.J., Jiménez Rugama, Ll.A.:
An adaptive algorithm employing continuous linear functionals. In: P. L'Ecuyer, B. Tu ff i n (eds.) Monte Carlo and Quasi-Monte Carlo Methods: MCQMC, Rennes, France, July 2018, Springer Proceedings in Mathematics and Statistics, vol. 324, pp. 161–181. Springer, Cham (2020). DOI: 10.1007/978-3-030-43465-6\_8 Ding, Y., Hickernell, F.J., Kritzer, P., Mak, S.: Adaptive approximation for multivariate linear problems with inputs lying in a cone. In: F.J. Hickernell, P. Kritzer (eds.) Multivariate Algorithms and Information-Based Complexity, pp. 109–145. DeGruyter, Berlin/Boston (2020). DOI: 10.1515/9783110635461-007} Emenike, O., Hickernell, F.J., Kritzer, P.: A uni fi ed treatment of tractability for approximation problems de fi ned on Hilbert spaces. J. Complexity 84, 101856 (2024). DOI: 10.1016/j.jco.2024.101856 Krieg, D., Kritzer, P.: Homogeneous algorithms and solvable problems on cones. J.\ Complexity 83, 101840 (2024). DOI: 10.1016/j.jco.2024.101840 Novak, E., Woźniakowski, H.: Tractability of Multivariate Problems Volume I: Linear Information. No. 6 in EMS Tracts in Mathematics. European Mathematical Society, Zürich (2008) Novak, E., Woźniakowski, H.: Tractability of Multivariate Problems Volume III: Standard Information for Operators. No. 18 in EMS Tracts in Mathematics. European Mathematical Society, Zürich (2012) 14