Unified Tractability MCM 2025

Talk given at Illinois Institute of Technology for MCM 2025

Transcript

1. Fred J. Hickernell, Illinois Institute of Technology Monte Carlo Methods, July 30, 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
2. 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
3. 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="WqGE8JuHRENfCCLlS3Eq28njFY4=">AAADInicfVJda9RAFE3iV40f3eqjL4NLoYVlSfqwFaHQVpA+VFy12xZ2YpxMbnbHTSZxZrLuMuTf+Gt8E30R/DFOshFqV7wwcDj33plzz52oSJlUnvfTdm7cvHX7zsZd9979Bw83O1uPzmVeCgojmqe5uIyIhJRxGCmmUrgsBJAsSuEimr2o8xdzEJLl/EwtCwgyMuEsYZQoQ4WdH3iMM6KmItNHw2EVxjtJj++iA4RlmYWaHfjVe47+lLx7fVqXlCbRi6tdhHsIlzwGEQlCQeOU8EkKKOmhtgSLhqlCjRUslEw0bjTrGSx5ruA4LaFiMZAUVfizAVOidFKtmisXfypJjP7TmjDOFKCXxg4GAhnNFQ7csNP1+l4TaB34LehabQzDLXuA45yWGXBFUyLl2PcKFWgiFKNGvruNSwkFoTMygbGBnGQgA90IqtC2YWKU5MIcrlDDulc7Fr7fdPRQPGeFbLGcT1qkiNlXoBer+1wcgxkM1sfVJ2evTivtefuD46Pq6hOaZFIus8iIqXclr+dq8l+5camSZ4FmvCgVcLqaJSlTpHJU/xcUMwFUpUsDCBXM+IHolJh1K/Oraqf9676ug/O9vj/oD97sdQ/ftp5vWE+sp9aO5Vv71qF1Yg2tkUXt5/YHm9kfnS/OV+eb831V6thtz2Prr3B+/QY1uQPT</latexit> APPd(f, n) = n i=1 SOLd(ui,d) →f, ui,d ↑ ideal fi,d finite Fourier sum Sequence of Ideal Linear Problems on Hilbert Spaces 3
4. of 14 4 <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
5. of 14 5 How does increase as and ? <latexit sha1_base64="zT2tIJgfwhoiJ1NMfE0s46BJBLg=">AAAEtHicfVPbThRBEB3WVXG9gT760pGQgK5khwcwJCSAiZKIuEYuJvQ66empWTr09IzdPcim09/lt/jgq/6GNbNDZGFjP53U5VSdquq4kMLYXu/nTOtW+/adu7P3OvcfPHz0eG7+yZHJS83hkOcy119iZkAKBYdWWAlfCg0siyUcx2dvKv/xOWgjcnVgRwUMMjZUIhWcWTRF860+jWEolBsyewr6he/QDJHO3Ha/76NkKe2qZbKxSagps8iJzdB/VeQy5vPHvSqmREc38cuEdgktVQI61oyDo5KpoQSSdkkTQnVt8ZGj30UCp8y61I9dntBvJUsItXBhTdpxtFbnzmCkcgs7sgSfCiUskLeoXoAm2BJm0Q6VR6Dt9a7SZfKK3FCzj6XPmYbCCJmrbu03XLsddFcKdEWFMZWdM+neVXZCUcWVNGx13GuaayYlSQkValL6BG80TYxrlLoSRZEYebz3lZrGjNzEkwnW/zY/vcolm1DIl9VbJzzPCgkXwo5w6rjarGreqbGIijOO3b6PemQDheMtJSxy6mXYnTYIPBhQyb/z6URzC72VXv3ITRA2YCFoXj+an3lPk5yXGSjLJTPmJOwVduCYtoLjrXQWaWmgYPyMDeEEoWIZmIGrtXqyiJaEVMNKc2VJbe1czbgIwzqjS5JzUZgGm/NhgyzDzzJwF2O+Dk0Azwym7Gv34MOed73e+trOtr9awrHMmFEWYzP1Rq77KuM030lp09cDXE1RWlB8rCUtJbE5qT4rSYQGbuUIAeNa4DwIP2V4Cha/9ESV+sxNajyOP7w+7JvgaHUlXFtZ+7S6sLXfLGI2eBY8D5aCMFgPtoLdoB8cBrz1o/Wr9bv1p73Wpm3ehnFoa6bJeRpMvLb6C297m/8=</latexit> APPd(f, n) := n i=1 SOLd(ui,d) →f, ui,d ↑ 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]
6. 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
7. of 14 7 <latexit sha1_base64="CDOdqC5L7xCv145dMxT7Jn4pOoU=">AAAIHXic3ZVPc9w0FMCd0u4WQ6GBI5c3ZNpJSgjrPaQcCFPSmdIZShto03Ym2npkW3Y0K8uOJWd20eiz9HPwAbgxvXb4NjzL3q03CZnhUA7osHor6f37+ekpKgVXejT6a+3KB1evDYbXP/Q/+vjGJ5/eXP/suSrqKmaHcSGK6mVEFRNcskPNtWAvy4rRPBLsRTS93+y/OGWV4oV8puclm+Q0kzzlMdW4FK5f+51ELOPSUMEzecf6JKf6WMWVeWDDBG4D0Wymq9zAMVWAnrgCCyTiWSaAGJQKkah5jpOZWVQulS6AlFWRhIYwgYe4BGc0rejU1NaCIS5uM2VzWWi2L2pmSUbznIZOY+qmV+ZrQkV5TFGDqJNKmzEKGZNoJzbEWEOsNSMotTWBbWwq/FVcWtiEMYbAO0Mwc9MW2QayzzMgyEND868X+9RiuCtRLuOOIvPYvlrdReWVpDDCOlJMsxOEEuCuSAqttiEhFlpalZPIO74/vje+/w9aC1bI5umTRwhrM91CXnuQAjk5qWnSolPpReWU1jJuChxoiahmPHflDkUFFYsLTGnu7Bsi8KokNDR8O7EEs+LoIGji5zLVc+sc9r7G5dwvqeH/nOOy6Jo8VV2GJjlj3Knny5TbjIG4gmlKpI8GEylRwXc4/slaD84eGkwW4I4ggK9g3OFxB2zrerrXZz1tvCx5ufhhAv6/8Xipy9+Yppudg613DhDQbfgOFvnzNL2wQ5XwPQTftNrL0gMqE1iAbLzs9Uj2ymFh3nfmH+PZU1qxUnFRyG1Y9oR9LHO0JhjcD0vonWn5+4TJZNmpw5sbo52RG3BeCDphw+vGQbi+9hNJirjOmdSxoEodBaNSTwytNI8Fs/4tUitW0nhKM3aEoqQ5UxPjWFi4hSsJpHiH0kJqcKt+X2MWBE4DC/CUl6qT1WnWSZriqzQxs9aeTxKW4qt1nrR5+OznR9isRnd393+wfReG5qq5OhiMQ3Z2r1m8aO+o1um3E8NlWWsm4zaXtBaAvbR5FSHh2Be0mKNA44ojD4iPKd4EjW/nihfXklSqLOIPzsI+Lzwf7wS7O7u/jDfu/dp9iOveF96X3qYXeHe9e95D78A79OIBDB4MngwOhq+Hfwz/HL5pj15Z63Q+91bG8O3fwHraQw==</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 d ω=1 1 + 2ωω ↓ k=1 k↑pε = sup d→N d ω=1 1 + 2ωωϖ(pϱ) < ↘ ≃⇐ p > 1/ϱ and ↓ ω=1 ωω < ↘ ≃⇐ Nϑ,Bd ⇒ Cpς↑p Strong Tractability for Approximation of Periodic Functions
8. 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
9. of 14 9 Includes algebraic/exponential (strong) (quasi-)polynomial tractability <latexit sha1_base64="Qc2Q7IddJmgMH/L4SZFJxh+ZEnA=">AAAERXicdVNLbxMxEN4mPEp4tXDkMqICpRCi3SIVhECq1AsHVBUpfUhxuvJ6vRurXu+y9pZGlv8cF+7c+AdcOIAQV5hNQknT1FrvjMcz428+j6NCCm18/+tSo3nl6rXryzdaN2/dvnN3ZfXevs6rkvE9lsu8PIyo5lIovmeEkfywKDnNIskPouPtev/ghJda5KpnRgUfZDRVIhGMGjSFq40+iXgqlKVSpOqJm13x2LVIpWJeRiVl3O6ElpzQkhdayFx1YufQMIZgI1lxRww/NWVmhUryMusCy7Oi6xw8hjdAMqGAWJy1zKgZRpHdcaEPr4BIxBvT0KqnAWbFNYeZg4BMTNt4WpTLWI8yFLbAzKQDPRKJVLZn/I/ss8B1SMpVgrAtsc4S56xfGGeD8Re7DpxPBXWWcp2Q1lkRSYLWDxWNET8Qfop3oeHdAgzTAPgozBActIiuitDGc5Wio66y0IqaDMkTg3/GhVyUsjd2aPuXFPH8XxHzNZQiHZr1qURR53dHiCMxIyDjRBjYa58RLpDuCV2w+KiNS/had/AaJolbhKv4rGH+L564Vriy5nf98YCLSjBV1rzp2A1XvpA4Z1XGlWGSat0PEMXA0tIIJnndjZoXlB3TlPdRVTTjemDHLejgEVpiwNbDqQyMrbMRlma6LgA961vR83u1cdFevzLJywF2dVEZrtjkoKSSYHKonxTEouTMyBEqlJUCsQIbUuTS4MOrSQjmS76o7G90g83u5vuNta2dKR3L3gPvodf2Au+Ft+W99Xa9PY81PjW+NX40fjY/N783fzV/T1wbS9OY+9650fzzF8RbdZc=</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]
10. of 14 10 <latexit sha1_base64="qzcraPgjLIZ7zO/WNyeaVSEHBpg=">AAAG63ichVRNb9w2EJVTe5tuPxK3xx46qLHAOl27qz24RtEArgMkPRSum9ZOANMWKImSuaYomaQcLwj+ifZW9Nof1Z/SW4eS7PXaC0QHacQZct68ecO4Elyb8fjflUcfrK71Pnz8Uf/jTz797MnT9c+PdVmrhB0lpSjV25hqJrhkR4Ybwd5WitEiFuxNfPHC+99cMaV5KX83s4qdFjSXPOMJNbgUra/+QWKWc2lzas6Zeub6MhrDDyCjsHlP8E2StDR6BOTysqYpEM3zgkbTYbYJ38NzIDHPBRBxzJSBIRGYPKWR5aPUAXnHU3ZOjc1cu7KJn+cystOt0H0TujMro6lrjlBAlD8ishNHSJ8UCEgnyr5wUTrPQyxkQLiExp9QYV96P0F0Vz6/N1p8duo8QiIYxnJMGTa2woIwI4X4TM1Dt9QtCIepLGmYtRdsJkvD9kXNnCWGXRud2aSUDMoMJE8YZLVMPJPaOUQN/UGDSxX2x8NDBDbMRhJZQvC6LnzpWHKHHWN+++VnH1N31DTga5kyFSuaMItUyhwhZyPoQohqVpDLB8Qi/rY7Lcr+YFkNGZfcMHiJ6uFMAWLCbch127t7sJC8LXhQzgHmvqKKVZqLUo4W2jTKfBFdF28b9Ao9ru3DfOOtmLJSUSHuNvXmNA+soxyDwMECOe/B4SnSdawNTS6WMTFvZlHVphkGKiAptfGMwJIdQGhVqfL6hmELXCKuYpuAP0Swa25mqAKUj9f32TM36lrSx59GA4UvEVXmx8VO5xXHsT1wqPG7k9XwlWGpdoE1fakMKnkL5TtxztK41W0rXGRsWa3voapJ5WPKguXUD9M8+NtOGtliW/1uP3e+xJv//bbNd0XYjgoVOXIkGVViBlRDXpap/8a+797pXJ8wmd5eQdHTjfH2uHngoRF2xkbQPYfR+soeScukLpg0iaBan4TjypxaqgxPcFz6pNasQiXQnJ2gKWnB9KltmHIwwJUUvMSyUhpoVu/usLTQelYg04Om1vs+v7jMd1KbbPfUcokCYzJpE2W1AFOCv4oh5YolBklJOU0UR6yQnFNsucELeyHLdQu1T1KGI8yWXE6vX+07Ox6F4e4o3N3BWRnAa1YJnBR4x805zHDkl5TWTLfOtOc8vM/wQ+N4sh3ubO/8OtnYO+jYfxx8GXwdDIMw+C7YC34KDoOjIFn9b+2rteHaZq/o/dn7q/d3G/popdvzRbDw9P75H4rSZJk=</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(f) ↑ ϑ ↘ 1 ↔ b2 ab Nω,Cd,f ↑ Nεdω/↗f↗Fd ,Bd cone alg. nearly as good as ball alg. Infer Bound on from Data [Ding, H, & Jiménez Rugama 2020] ∥f∥ℱd
11. of 14 11 <latexit sha1_base64="Qhz24daTbpDi30vf3Pvgvg/aSHU=">AAADvnicbVNbT9swGE3pLqy7ANvjXj4NIcEoKKkmhqYhVSBte5oYGhcJl8hxvrQujlNsB6gs/8P9gf2NvW4Pc9JqHRdLUY6+2zk++ZKMBNcmDH825poPHj56PP+k9fTZ8xcLi0svj3RRKoaHrBCFOkmoRsElHhpuBJ6MFNI8EXicnO9V+eNLVJoX8rsZj7CX077kGWfU+FC81ECSYJ9L26dmgOqta8l4CDvQObPD9XeuDUMgXALJfTpJ7FcXh20gFxclTYFo3s9pPFzN1uCD7yEJ7wsg4giVgVUivIqUxpa3Uwfkiqc4oMZmbhJZ868dGdvhRuTWI3dmPa+rRyggqhoR244jpFVTa6bsnovTGQ+xkM2kMSrspypPvLrLir8CE3126CqFRKCv5Z4yqrGCj+AZ/UU3lBcwq95Q/3Q4z2ZJ7bI9x7EsDO6KEp0lBq+NziwrJEKRgeQMISslq1zVzrkWQZnOTI0Xl8PNsD5wF0RTsBxMz77/MF2SFqzMURomqNanUTgyPUuV4Uygn19qHFF2Tvt46qGkOeqeraU6WPGRFLJC+UcaqKP/d1iaaz3OE19Zu3s7VwXvy52WJtvuWS5HpUHJJkRZKcAUUG0XpFwhM2LsAWWKe63ABlRRZvwO3mC5nkhtkRQzv7v3eHzwedfZsB1F2+1oe8sBrMABjgT1Tl9xM4Cx/wfuuVolWulMO+95dNvhu+CosxltbW596yx3D6buzwevgzfBahAF74Nu8CXYDw4D1vjR+NX43fjT7DazZt4sJqVzjWnPq+DGaV7/BQDxNUU=</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
12. of 14 12 <latexit sha1_base64="Qhz24daTbpDi30vf3Pvgvg/aSHU=">AAADvnicbVNbT9swGE3pLqy7ANvjXj4NIcEoKKkmhqYhVSBte5oYGhcJl8hxvrQujlNsB6gs/8P9gf2NvW4Pc9JqHRdLUY6+2zk++ZKMBNcmDH825poPHj56PP+k9fTZ8xcLi0svj3RRKoaHrBCFOkmoRsElHhpuBJ6MFNI8EXicnO9V+eNLVJoX8rsZj7CX077kGWfU+FC81ECSYJ9L26dmgOqta8l4CDvQObPD9XeuDUMgXALJfTpJ7FcXh20gFxclTYFo3s9pPFzN1uCD7yEJ7wsg4giVgVUivIqUxpa3Uwfkiqc4oMZmbhJZ868dGdvhRuTWI3dmPa+rRyggqhoR244jpFVTa6bsnovTGQ+xkM2kMSrspypPvLrLir8CE3126CqFRKCv5Z4yqrGCj+AZ/UU3lBcwq95Q/3Q4z2ZJ7bI9x7EsDO6KEp0lBq+NziwrJEKRgeQMISslq1zVzrkWQZnOTI0Xl8PNsD5wF0RTsBxMz77/MF2SFqzMURomqNanUTgyPUuV4Uygn19qHFF2Tvt46qGkOeqeraU6WPGRFLJC+UcaqKP/d1iaaz3OE19Zu3s7VwXvy52WJtvuWS5HpUHJJkRZKcAUUG0XpFwhM2LsAWWKe63ABlRRZvwO3mC5nkhtkRQzv7v3eHzwedfZsB1F2+1oe8sBrMABjgT1Tl9xM4Cx/wfuuVolWulMO+95dNvhu+CosxltbW596yx3D6buzwevgzfBahAF74Nu8CXYDw4D1vjR+NX43fjT7DazZt4sJqVzjWnPq+DGaV7/BQDxNUU=</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)
13. 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
14. 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