\BOOKMARK [1][-]{section.1}{Introduction}{}% 1
\BOOKMARK [1][-]{section.2}{Outline of contributions}{}% 2
\BOOKMARK [1][-]{section.3}{Setting}{}% 3
\BOOKMARK [2][-]{subsection.3.1}{Definitions and notation}{section.3}% 4
\BOOKMARK [2][-]{subsection.3.2}{Precise assumptions on reproducing kernel Hilbert space}{section.3}% 5
\BOOKMARK [1][-]{section.4}{Equivalence of the infinite-dimensional problem}{}% 6
\BOOKMARK [1][-]{section.5}{Properties of the finite-dimensional problem}{}% 7
\BOOKMARK [2][-]{subsection.5.1}{Uniform inequality from scattered constraints}{section.5}% 8
\BOOKMARK [2][-]{subsection.5.2}{Convergence properties of the finite-dimensional problem}{section.5}% 9
\BOOKMARK [2][-]{subsection.5.3}{Result for Sobolev kernels and discussion}{section.5}% 10
\BOOKMARK [1][-]{section.6}{Algorithm}{}% 11
\BOOKMARK [1][-]{section.7}{Finding the global minimizer}{}% 12
\BOOKMARK [2][-]{subsection.7.1}{Algorithm}{section.7}% 13
\BOOKMARK [2][-]{subsection.7.2}{Warm restart scheme for linear rates}{section.7}% 14
\BOOKMARK [1][-]{section.8}{Extensions}{}% 15
\BOOKMARK [2][-]{subsection.8.1}{Approximate solutions}{section.8}% 16
\BOOKMARK [2][-]{subsection.8.2}{Rates for f with low smoothness}{section.8}% 17
\BOOKMARK [2][-]{subsection.8.3}{Certificate of optimality}{section.8}% 18
\BOOKMARK [1][-]{section.9}{Relationship with polynomial hierarchies}{}% 19
\BOOKMARK [1][-]{section.10}{Experiments}{}% 20
\BOOKMARK [1][-]{section.11}{Discussion}{}% 21
\BOOKMARK [1][-]{appendix.A}{Additional notation and definitions}{}% 22
\BOOKMARK [2][-]{subsection.A.1}{Fourier Transform.}{appendix.A}% 23
\BOOKMARK [2][-]{subsection.A.2}{Sobolev Spaces}{appendix.A}% 24
\BOOKMARK [2][-]{subsection.A.3}{Reproducing Kernel Hilbert spaces}{appendix.A}% 25
\BOOKMARK [2][-]{subsection.A.4}{Auxiliary results on C functions}{appendix.A}% 26
\BOOKMARK [1][-]{appendix.B}{Fundamental results on scattered data approximation}{}% 27
\BOOKMARK [1][-]{appendix.C}{Auxiliary results on RKHS}{}% 28
\BOOKMARK [2][-]{subsection.C.1}{Proof of prop:properties-V}{appendix.C}% 29
\BOOKMARK [1][-]{appendix.D}{The constants of translation invariant and Sobolev kernels}{}% 30
\BOOKMARK [2][-]{subsection.D.1}{Results for translation invariant and Sobolev kernels}{appendix.D}% 31
\BOOKMARK [2][-]{subsection.D.2}{Proof of prop:sobolev-kernel}{appendix.D}% 32
\BOOKMARK [1][-]{appendix.E}{Proofs for alg:glm}{}% 33
\BOOKMARK [2][-]{subsection.E.1}{Proof of thm:fill-distance-random-points}{appendix.E}% 34
\BOOKMARK [2][-]{subsection.E.2}{Proof of thm:alg-glm}{appendix.E}% 35
\BOOKMARK [1][-]{appendix.F}{Global minimizer. Proofs.}{}% 36
\BOOKMARK [2][-]{subsection.F.1}{Proof of rm:existence-beta}{appendix.F}% 37
\BOOKMARK [2][-]{subsection.F.2}{Proof of thm:Hilbert-z-isgood}{appendix.F}% 38
\BOOKMARK [2][-]{subsection.F.3}{Proof of thm:bound-prob-sampled-z}{appendix.F}% 39
\BOOKMARK [1][-]{appendix.G}{Proofs for the extensions}{}% 40
\BOOKMARK [2][-]{subsection.G.1}{Proof of thm:appr-solution}{appendix.G}% 41
\BOOKMARK [2][-]{subsection.G.2}{Proof of cor:g-in-Cs-has-A}{appendix.G}% 42
\BOOKMARK [2][-]{subsection.G.3}{Proof of thm:Aeps-exists}{appendix.G}% 43
\BOOKMARK [2][-]{subsection.G.4}{Proof of thm:global-min-low-smoothness}{appendix.G}% 44
\BOOKMARK [2][-]{subsection.G.5}{Certificate of optimality for the global minimizer candidate of eq:prob-relax-z}{appendix.G}% 45