Monte Carlo Methods for Uniform Approximation on Periodic Sobolev Spaces with Mixed Smoothness
Provides theoretical convergence rates for Monte Carlo methods in high-dimensional approximation, relevant for numerical analysts working on function approximation.
The paper determines the order of convergence for Monte Carlo approximation of embeddings from periodic Sobolev spaces with mixed smoothness into L∞, achieving up to 1/2 speedup in the main rate compared to worst-case approximation, and resolving open cases from Fang and Duan.
We consider the order of convergence for linear and nonlinear Monte Carlo approximation of compact embeddings from Sobolev spaces of dominating mixed smoothness defined on the torus $\mathbb{T}^d$ into the space $L_{\infty}(\mathbb{T}^d)$ via methods that use arbitrary linear information. These cases are interesting because we can gain a speedup of up to $1/2$ in the main rate compared to the worst case approximation. In doing so we determine the rate for some cases that have been left open by Fang and Duan.